ABC 325

Table of Contents

E - Our clients, please wait a moment

https://atcoder.jp/contests/abc325/tasks/abc325_e

類題: https://atcoder.jp/contests/abc395/tasks/abc395_e

社用車だけを使ったときの場合のグラフ $G$ と電車だけを使った場合のグラフ $G^\prime$ を作り、$G$ の各ノードから同じ都市に対応する $G^\prime$ のノードへコスト 0 の辺を張る。

都市 $i$ に対応する $G$ におけるノード番号を $i$, $G^\prime$ におけるノードの番号を $N + i$ とする。 求める答えはノード 1 から出発してノード $N$ またはノード $2N$ に到達するまでの最小コストである。 ($1 \rightarrow N+1$ への移動はコスト 0 でできるから出発は 1 から出発するケースだけ考えればよい)

struct Edge {
    ll to, cost;
};

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, a, b, c;
    cin >> n >> a >> b >> c;

    vvll D(n, vll(n));
    rep(i, n) rep(j, n) cin >> D[i][j];

    vector<vector<Edge>> graph(n * 2);
    rep(i, n) rep(j, n) {
        if (i == j)
            continue;
        graph[i].push_back({j, D[i][j] * a});
        graph[j].push_back({i, D[i][j] * a});
        graph[n + i].push_back({n + j, D[i][j] * b + c});
        graph[n + j].push_back({n + i, D[i][j] * b + c});
    }
    rep(i, n) graph[i].push_back({n + i, 0});

    vll dist(n * 2, INF);
    dist[0] = 0;

    // cost, pos
    using P = pair<ll, ll>;
    priority_queue<P, vector<P>, greater<P>> pq;

    pq.push({0, 0});
    while (pq.size()) {
        auto [cost, now] = pq.top();
        pq.pop();

        if (dist[now] < cost)
            continue;

        for (auto [to, cost] : graph[now]) {
            if (dist[to] <= dist[now] + cost)
                continue;

            dist[to] = dist[now] + cost;
            pq.push({dist[to], to});
        }
    }

    cout << min(dist[n - 1], dist[n * 2 - 1]) << '\n';
}