This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A" #include <bits/stdc++.h> using namespace std; #include "../dijkstra.h" int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m, start; cin >> n >> m >> start; vector< vector<pair<int, ll>> > g(n); while (m--) { int u, v, c; cin >> u >> v >> c; g[u].push_back({v, c}); } auto [dist, trace] = dijkstra(g, start); for (auto d : dist) { if (d == INF) cout << "INF\n"; else cout << d << '\n'; } return 0; }
#line 1 "Graph/tests/aizu_grl_1_a_dijkstra_aizu.test.cpp" #define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A" #include <bits/stdc++.h> using namespace std; #line 1 "Graph/dijkstra.h" // Dijkstra // // Notes: // - Index from 0 // // Tested: // - https://judge.yosupo.jp/problem/shortest_path // // Param: // - g[u] = pair<v, cost>, adjacency list // - start = start vertex // Returns: // - distances from start. If unreachable -> dist = INF // - previous vertex. Previous[start] = start. If unreachable -> trace = -1 // Dijkstra {{{ using ll = long long; const ll INF = 1e18; // must be greater than maximum possible path pair<vector<ll>, vector<int>> dijkstra(const vector<vector<pair<int, ll>>>& g, int start) { int n = g.size(); vector<ll> f(n, INF); vector<int> trace(n, -1); f[start] = 0; trace[start] = start; using P = pair<ll, int>; // <distance, vertex> // priority_queue should be faster than set? priority_queue<P, vector<P>, greater<P>> all; all.push(P{0LL, start}); while (!all.empty()) { auto [dist, u] = all.top(); all.pop(); if (dist != f[u]) continue; for (auto [v, c] : g[u]) { if (f[v] > f[u] + c) { f[v] = f[u] + c; trace[v] = u; all.push(P{f[v], v}); } } } return {f, trace}; } // Dijkstra from start -> target // Returns: // - distance. If unreachable -> INF // - path. If unreachable -> {} pair<ll, vector<int>> dijkstra(const vector<vector<pair<int, ll>>>& g, int start, int target) { auto [f, trace] = dijkstra(g, start); if (trace[target] < 0) { return {INF, {}}; } vector<int> path; for (int u = target; u != start; u = trace[u]) { path.push_back(u); } path.push_back(start); reverse(path.begin(), path.end()); return {f[target], path}; } // }}} #line 7 "Graph/tests/aizu_grl_1_a_dijkstra_aizu.test.cpp" int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m, start; cin >> n >> m >> start; vector< vector<pair<int, ll>> > g(n); while (m--) { int u, v, c; cin >> u >> v >> c; g[u].push_back({v, c}); } auto [dist, trace] = dijkstra(g, start); for (auto d : dist) { if (d == INF) cout << "INF\n"; else cout << d << '\n'; } return 0; }