ABC362 D-Shortest Path 3 (C++)

D - Shortest Path 3

検討

DFSとかで書けないかなといじいじしたもののさっぱり分からず、解説を読んでダイクストラ法の存在を知りました。回答に当たっては下記サイトを大いに参考にさせていただきました。

ダイクストラ法の理解に苦戦したので個人的メモ - Qiita

回答

#include <bits/stdc++.h>
using namespace std;

struct p {
    int dest;
    int val;
};

int main() {
    int N, M; cin >> N >> M;
    vector<int> vertex(N+1);
    for (int i = 1; i <= N; i++) cin >> vertex[i];
    vector<vector<p>> path(N+1);
    for (int i = 0; i < M; i++) {
        int U, V, B; cin >> U >> V >> B;

    // 普通のダイクストラ法では頂点の重みを考慮できないので、辺に足す
        p B1 = {U, B + vertex[U]};
        p B2 = {V, B + vertex[V]};
        path[V].push_back(B1);
        path[U].push_back(B2);
    }

    // 最速距離のリスト デカ値で埋めておく
    vector<int64_t> dist(N+1, INT64_MAX);

    // 探索中の現在地をpairで管理する 距離、現在地
    using clocation = pair<int64_t, int>;

    // 小さい順に取り出したいので、priority_queue の小さい順を使う
    priority_queue<clocation, vector<clocation>, greater<clocation>> que;
    que.push({vertex[1],1});

    // ダイクストラ法の本体
    while(!que.empty()) {
        clocation c = que.top();
        que.pop();
        if (c.first > dist[c.second]) {
            continue; // 距離リストを参照し、最短でなければ打ち切り
        }
        for (auto desti : path[c.second]) { // 各nodeにアクセス
            int to = desti.dest;
            int64_t cost = desti.val;
            if (c.first + cost < dist[to]) {
                dist[to] = c.first + cost;
                que.push({dist[to], to});
            }
        }
    }

    for (int i = 2; i <= N; i++) {
        cout << dist[i] << " ";
    }

    return 0;
}

実行時間289msでACでした。

自分の覚書用に以下にメモを残しておきます。

memo

・ダイクストラ法の肝は最短距離のメモ
スタートから各点までの最短距離を知りたいので、最短以外のルートはどうでもいい。探索済みの地点とそこまでの最短距離をpriority_queueで管理する。
・探索結果は別のリストで管理

    // ダイクストラ法の本体
    while(!que.empty()) {
        clocation c = que.top();
        que.pop();

現在地を移動する過程でpopするので、距離の値は別のリストで管理する。