This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub
#define PROBLEM "https://judge.yosupo.jp/problem/shortest_path" #include <iostream> #include "C++/graph/WeightedGraph.hpp" int main() { int n, m, s, t; std::cin >> n >> m >> s >> t; w_graph<false> g(n, 0); g.input(m); auto dj = g.dijkstra(s); if(!dj.is_thru(t)) { std::cout << "-1\n"; return 0; } const auto ed = dj.path(t); std::cout << dj.get()[t] << ' '; const int len = ed.size() - 1; std::cout << len << '\n'; for(int i = 0; i < len; ++i) { std::cout << ed[i] << ' ' << ed[i + 1] << '\n'; } }
#line 1 "test/shortestpath.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/shortest_path" #include <iostream> #line 2 "C++/graph/WeightedGraph.hpp" #line 2 "C++/graph/Graph.hpp" #line 4 "C++/graph/Graph.hpp" #include <vector> #include <algorithm> #include <queue> #include <stack> #ifndef TEMPLATE template <class T, class U> bool chmin(T& a, const U& b){ if(a>b){ a=b; return 1; } return 0; } #endif #line 2 "C++/graph/edge.hpp" struct edge { int src, to, id; long long cost; edge(){} edge(const int src_, const int to_, const int id_ = -1, const long long cost_ = 0): src(src_), to(to_), id(id_), cost(cost_){} operator int() const { return to; } }; /** * @brief Edge */ #line 12 "C++/graph/Graph.hpp" template <bool undirected = true> struct graph: std::vector<std::vector<edge>> { protected: int indexed, id; std::vector<edge> edges; public: graph(){} graph(const int n, const int indexed_ = 1): indexed(indexed_), id(0){ this -> resize(n); } void add(int a, int b) { a -= indexed, b-= indexed; (*this)[a].emplace_back(a, b, id); edges.emplace_back(a, b, id++); if(undirected) { (*this)[b].emplace_back(b, a, --id); edges.emplace_back(b, a, id++); } } void input(const int m) { for(int i = 0; i < m; ++i) { int a, b; std::cin >> a >> b; add(a, b); } } std::vector<edge> get_edge() const { return edges; } std::vector<int> all_dist(const int v) { std::vector<int> d(this -> size(), -1); std::queue<int> q; d[v] = 0; q.emplace(v); while(q.size()) { const int tmp = q.front(); q.pop(); for(const auto &el: (*this)[tmp]) { if(d[el] != -1) { continue; } d[el] = d[tmp] + 1; q.emplace(el); } } return d; } int dist(const int u, const int v){ return all_dist(u)[v]; } std::vector<int> t_sort() { const int n = this -> size(); std::vector<int> deg(n); for(int i = 0; i < n; ++i) { for(const auto ed: (*this)[i]) { deg[ed]++; } } std::stack<int> sk; for(int i = 0; i < n; ++i) { if(deg[i] == 0) { sk.emplace(i); } } std::vector<int> ord; while(sk.size()) { const auto tmp = sk.top(); sk.pop(); ord.emplace_back(tmp); for(const auto ed: (*this)[tmp]) { if(--deg[ed] == 0) { sk.emplace(ed); } } } return ord.size() == size() ? ord : std::vector<int>{}; } std::vector<edge> cycle() { const int n = size(); std::vector<int> used(n); std::vector<edge> pre(n), cycle; const auto dfs = [&](const auto &f, const int i) -> bool { used[i] = 1; for(const auto &e: (*this)[i]) { if(used[e] == 0) { pre[e] = e; if(f(f, e)) { return true; } } else if(used[e] == 1) { int now = i; while(now != e) { cycle.emplace_back(pre[now]); now = pre[now].src; } cycle.emplace_back(e); return true; } } used[i] = 2; return false; }; for(int i = 0; i < n; ++i) { if(used[i] == 0 && dfs(dfs, i)) { std::reverse(cycle.begin(), cycle.end()); return cycle; } } return {}; } }; typedef std::vector<edge> ve; typedef std::vector<ve> we; /** * @brief グラフライブラリ */ #line 2 "C++/graph/ShortestPath.hpp" #pragma GCC diagnostic ignored "-Wreorder" #line 7 "C++/graph/ShortestPath.hpp" struct ShortestPath { private: const std::vector<long long> cost; const std::vector<int> src; public: ShortestPath(const std::vector<long long> &cost, const std::vector<int> &src): cost(cost), src(src){} bool is_thru(const int i){ return src[i] != -1; } std::vector<int> path(int i) { std::vector<int> res; for(; i != -1; i = src[i]) { res.emplace_back(i); } std::ranges::reverse(res); return res; } std::vector<long long> get() const { return cost; } }; /** * @brief 最短路 */ #line 5 "C++/graph/WeightedGraph.hpp" template <bool undirected = true> struct w_graph: graph<undirected> { protected: using graph<undirected>::indexed; using graph<undirected>::id; using graph<undirected>::edges; public: w_graph(const int n, const int indexed_ = 1): graph<undirected>(n, indexed_){} using graph<undirected>::get_edge; using graph<undirected>::all_dist; using graph<undirected>::dist; using graph<undirected>::t_sort; using graph<undirected>::cycle; void add(int a, int b, const long long cost) { a -= indexed, b -= indexed; (*this)[a].emplace_back(a, b, id, cost); edges.emplace_back(a, b, id++, cost); if(undirected) { (*this)[b].emplace_back(b, a, --id, cost); edges.emplace_back(b, a, id++, cost); } } void input(const int m) { for(int i = 0; i < m; ++i) { int a, b; long long c; std::cin >> a >> b >> c; add(a, b, c); } } ShortestPath dijkstra(const int v) { std::vector<long long> cst(this -> size(), (1LL << 61) - 1); std::vector<int> src(this -> size(), -1); std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<std::pair<long long, int>>> dj; cst[v] = 0; dj.emplace(cst[v], v); while(dj.size()) { const auto tmp = dj.top(); dj.pop(); if(cst[tmp.second] < tmp.first) { continue; } for(const auto &el: (*this)[tmp.second]) { if(chmin(cst[el], tmp.first + el.cost)) { src[el] = tmp.second; dj.emplace(cst[el], el); } } } return {cst, src}; } std::vector<long long> spfa(const int v) { const int n = this -> size(); std::vector<long long> cst(n, (1LL << 61) - 1); std::vector<int> pending(n), times(n); std::queue<int> q; q.emplace(v); pending[v] = 1; ++times[v]; cst[v] = 0; while(!q.empty()) { const int p = q.front(); q.pop(); pending[p] = 0; for(const auto &e : (*this)[p]) { const long long next = cst[p] + e.cost; if(next >= cst[e]) { continue; } cst[e] = next; if(!pending[e]) { if(++times[e] >= n) { cst.clear(); return cst; } pending[e] = 1; q.emplace(e); } } } return cst; } std::vector<std::vector<long long>> warshall_floyd() { const int n = this -> size(); const long long lim = (1LL << 61) - 1; std::vector cst(n, std::vector(n, lim)); for(int i = 0; i < n; ++i) { cst[i][i] = 0; } for(int i = 0; i < n; ++i) { for(const auto &j: (*this)[i]) { cst[i][j] = j.cost; } } for(int k = 0; k < n; ++k) { for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { if(cst[i][k] == lim || cst[k][j] == lim) { continue; } chmin(cst[i][j], cst[i][k] + cst[k][j]); } } } return cst; } }; /** * @brief 重み付きグラフライブラリ */ #line 4 "test/shortestpath.test.cpp" int main() { int n, m, s, t; std::cin >> n >> m >> s >> t; w_graph<false> g(n, 0); g.input(m); auto dj = g.dijkstra(s); if(!dj.is_thru(t)) { std::cout << "-1\n"; return 0; } const auto ed = dj.path(t); std::cout << dj.get()[t] << ' '; const int len = ed.size() - 1; std::cout << len << '\n'; for(int i = 0; i < len; ++i) { std::cout << ed[i] << ' ' << ed[i + 1] << '\n'; } }