【競プロ典型90問】013 - Passing（★5）

概要・感想

ダイクストラ法の問題。典型的なダイクストラ法という感じで正直★5ではないようにも思うが、意外とこんなもん？

水色になってやっとダイクストラも書き慣れてきたと思うが、まだまだ何も考えずにかけるという境地には至らない。今回もpop()を忘れてバグらせてしまった。

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

using P = pair<int, int>;
int n, m;
vector<vector<P>> graph;
const int INF = 1e9;


void dijkstra(int s, vector<int> &dist) {
    dist.assign(n, INF);
    priority_queue<P, vector<P>, greater<P>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto tmp = pq.top();
        pq.pop();
        int d = tmp.first, v = tmp.second;
        if (dist[v] < d) continue;
        for (auto nxt: graph[v]) {
            int nd = d + nxt.second;
            int nv = nxt.first;
            if (nd < dist[nv]) {
                dist[nv] = nd;
                pq.push({nd, nv});
            }
        }
    }
}

int main() {
    cin >> n >> m;
    graph.assign(n, vector<P>(0));
    int a, b, p;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> p;
        a--, b--;
        graph[a].push_back({b, p});
        graph[b].push_back({a, p});
    }
    vector<int> from_1, from_n;
    dijkstra(0, from_1);
    dijkstra(n-1, from_n);
    for (int i = 0; i < n; i++) {
        cout << from_1[i] + from_n[i] << endl;
    }
}