This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub gyouzasushi/library
#define PROBLEM "https://judge.yosupo.jp/problem/shortest_path" #include <algorithm> #include <iostream> #include "graph/dijkstra.hpp" int main() { int n, m, s, t; std::cin >> n >> m >> s >> t; std::vector<std::vector<std::pair<int, long long>>> g(n); for (int i = 0; i < m; i++) { int a, b; long long c; std::cin >> a >> b >> c; g[a].emplace_back(b, c); } auto [dist, from] = dijkstra(s, g); if (dist[t] == std::numeric_limits<long long>::max()) { std::cout << -1 << '\n'; return 0; } int pos = t; std::vector<int> path; while (pos != -1) { path.push_back(pos); pos = from[pos]; }; std::reverse(path.begin(), path.end()); std::cout << dist[t] << ' ' << path.size() - 1 << '\n'; for (int i = 0; i + 1 < int(path.size()); i++) { std::cout << path[i] << ' ' << path[i + 1] << '\n'; } }
#line 1 "test/library-checker/shortest_path.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/shortest_path" #include <algorithm> #include <iostream> #line 2 "graph/dijkstra.hpp" #include <limits> #include <queue> #include <vector> template <typename T> std::pair<std::vector<T>, std::vector<int>> dijkstra( int s, const std::vector<std::vector<std::pair<int, T>>> &g) { std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<std::pair<T, int>>> que; int n = int(g.size()); std::vector<T> d(n, std::numeric_limits<T>::max()); std::vector<int> from(n, -1); d[s] = 0; que.emplace(0, s); while (!que.empty()) { auto [dist, pos] = que.top(); que.pop(); if (d[pos] < dist) continue; for (auto [to, cost] : g[pos]) { if (d[pos] + cost < d[to]) { d[to] = d[pos] + cost; from[to] = pos; que.emplace(d[to], to); } } } return {d, from}; } #line 6 "test/library-checker/shortest_path.test.cpp" int main() { int n, m, s, t; std::cin >> n >> m >> s >> t; std::vector<std::vector<std::pair<int, long long>>> g(n); for (int i = 0; i < m; i++) { int a, b; long long c; std::cin >> a >> b >> c; g[a].emplace_back(b, c); } auto [dist, from] = dijkstra(s, g); if (dist[t] == std::numeric_limits<long long>::max()) { std::cout << -1 << '\n'; return 0; } int pos = t; std::vector<int> path; while (pos != -1) { path.push_back(pos); pos = from[pos]; }; std::reverse(path.begin(), path.end()); std::cout << dist[t] << ' ' << path.size() - 1 << '\n'; for (int i = 0; i + 1 < int(path.size()); i++) { std::cout << path[i] << ' ' << path[i + 1] << '\n'; } }