#include <bits/stdc++.h> using namespace std; #define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_A" #include "../graph/dijkstra.cpp" #include "../template/const.hpp" int main() { int n, m, s; cin >> n >> m >> s; Dijkstra<int, INF> dij(n); for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; dij.add_edge(a, b, c); } auto dist = dij.solve(s); for (auto &a : dist) { if (a == INF) cout << "INF\n"; else cout << a << '\n'; } return 0; }
#line 1 "test/dijkstra.test.cpp" #include <bits/stdc++.h> using namespace std; #define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_A" #line 3 "graph/dijkstra.cpp" using namespace std; // Dijkstra // dijkstra法で最短経路を求める. template <typename T, const T INF> struct Dijkstra { using edge = pair<T, int>; int n; vector<vector<edge>> G; vector<T> dist; vector<int> prev; Dijkstra(int n) : n(n) { G.resize(n); dist.resize(n); prev.resize(n); } // add_edge // aからbへコストcの辺を張る // 制約: c >= 0 void add_edge(int a, int b, T c) { G[a].emplace_back(c, b); } // solve // sからの最短経路を求める. // 計算量: O(|E|log|V|) vector<T> solve(int s = 0) { fill(dist.begin(), dist.end(), INF); fill(prev.begin(), prev.end(), -1); dist[s] = 0; priority_queue<edge, vector<edge>, greater<edge>> q; q.push({0, s}); while (!q.empty()) { edge p = q.top(); q.pop(); auto [d, v] = p; if (dist[v] < d) continue; for (const auto &p : G[v]) { auto [cost, u] = p; if (dist[u] > dist[v] + cost) { dist[u] = dist[v] + cost; prev[u] = v; q.push({dist[u], u}); } } } return dist; } // restore_path // 頂点sからtまでの最短経路を求める。 // 最短経路が存在する場合, 返り値は先頭にs,tを含む. 存在しないとき空を返す. // 制約: sは以前にsolve(s)が呼ばれている. 0 <= t < n vector<int> restore_path(int s, int t) { if (dist[t] == INF) return {}; vector<int> ret; int now_v = t; ret.push_back(now_v); while (now_v != s) { now_v = prev[now_v]; ret.push_back(now_v); } reverse(ret.begin(), ret.end()); return ret; } }; #line 2 "template/const.hpp" constexpr int INF = 1000'000'000; constexpr long long HINF = 4000'000'000'000'000'000; constexpr long long MOD = 998244353; constexpr double EPS = 1e-6; constexpr double PI = 3.14159265358979; #line 7 "test/dijkstra.test.cpp" int main() { int n, m, s; cin >> n >> m >> s; Dijkstra<int, INF> dij(n); for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; dij.add_edge(a, b, c); } auto dist = dij.solve(s); for (auto &a : dist) { if (a == INF) cout << "INF\n"; else cout << a << '\n'; } return 0; }