けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 325 E - Our clients, please wait a moment (緑色, 450 点)

AtCoder AtCoder450点 ABC-E 緑色diff 密グラフ Dijkstra法グラフ最短路問題【問題集】最短路問題グラフや盤面が時間変化する最短路問題 DP状態:フェーズ(耳DP) グラフの頂点を倍加する典型要素を詰め合わせた教育的問題最小コスト所要時間を求める問題最適化問題

少し頂点を増やす感じの Dijkstra 法。とても教育的な典型問題！

問題へのリンク

問題概要

頂点数 $N$ の完全グラフが与えられる。頂点 1 から頂点 $N$ へと到達したい。途中までは社用車を使い、途中からは電車を使うことができる。電車から社用車に乗り換えることはできない。

頂点 $i$ から頂点 $j$ へと社用車で移動： $D_{i, j} \times A$ 分かかる
頂点 $i$ から頂点 $j$ へと電車で移動： $D_{i, j} \times B + C$ 分かかる

なお、社用車から電車に乗り換えるのにかかる時間は 0 分と考えてよい。頂点 1 から頂点 $N$ に到達するのにかかる最小時間を求めよ。

制約

$2 \le N \le 1000$

考えたこと

頂点が $N$ 個ではなく、 $2N$ 個になるタイプの Dijkstra 法。

頂点 $0, 1, \dots, N-1$ 同士の距離は、社用車用の距離の両向辺
頂点 $N, N+1, \dots, 2N-1$ 同士の距離は、電車用の距離の両向辺
頂点 $i$ ( $\le N-1$ ) から頂点 $i+N$ に対して、距離 0 の有向辺

というグラフ上で Dijkstra 法をすればよい。頂点 $N-1$ または頂点 $2N-1$ への最短路の最小値を答えればよい。

なお、密グラフなので、Dijkstra 法の距離値が最小の頂点を求める部分で、priority queue を使わずに愚直に求めた方が高速になる。その場合の計算量は $O(N^{2})$ となる (priority queue を使っても通るが、 $O(N^{2} \log N)$ となる)。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    long long N, A, B, C;
    cin >> N >> A >> B >> C;
    vector<vector<long long>> D(N, vector<long long>(N));
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) cin >> D[i][j];
    
    const long long INF = 1LL<<60;
    vector<long long> dp(N*2, INF), used(N*2, false);
    dp[0] = 0;
    for (int iter = 0; iter < N*2; ++iter) {
        // まだ使っていない頂点のうち、dp 値が最も小さいものを探す
        int v = -1;
        long long dist = INF;
        for (int i = 0; i < N*2; ++i) {
            if (used[i]) continue;
            if (chmin(dist, dp[i])) v = i;
        }
        if (v == -1) continue;
        
        // その頂点 v から、各頂点への移動をしていく
        if (v < N) {
            // フェーズ 2 への以降
            chmin(dp[v + N], dp[v]);
            
            // 各頂点への以降
            for (int v2 = 0; v2 < N; ++v2) {
                chmin(dp[v2], dp[v] + D[v][v2] * A);
            }
        } else {
            for (int v2 = N; v2 < N*2; ++v2) {
                chmin(dp[v2], dp[v] + D[v-N][v2-N] * B + C);
            }
        }
        used[v] = true;
    }
    cout << min(dp[N-1], dp[N*2-1]) << endl;
}