This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
#define PROBLEM "https://judge.yosupo.jp/problem/shortest_path" #include <bits/stdc++.h> using namespace std; #include "../dijkstra.h" #define SZ(x) ((int)(x).size()) #define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i) int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n, m, s, t; cin >> n >> m >> s >> t; // read edges vector<vector<pair<int,ll>>> g(n); while (m--) { int u, v, c; cin >> u >> v >> c; g[u].push_back({v, c}); } // output auto [dist, path] = dijkstra(g, s, t); if (dist == INF) { cout << -1 << endl; return 0; } cout << dist << ' ' << SZ(path) - 1 << '\n'; REP(i,SZ(path)-1) { cout << path[i] << ' ' << path[i+1] << '\n'; } return 0; }
#line 1 "Graph/tests/dijkstra.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/shortest_path" #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/dijkstra.test.cpp" #define SZ(x) ((int)(x).size()) #define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i) int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n, m, s, t; cin >> n >> m >> s >> t; // read edges vector<vector<pair<int,ll>>> g(n); while (m--) { int u, v, c; cin >> u >> v >> c; g[u].push_back({v, c}); } // output auto [dist, path] = dijkstra(g, s, t); if (dist == INF) { cout << -1 << endl; return 0; } cout << dist << ' ' << SZ(path) - 1 << '\n'; REP(i,SZ(path)-1) { cout << path[i] << ' ' << path[i+1] << '\n'; } return 0; }