This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub Harui-i/library
#include "graph/bellmanford.hpp"
負辺のあるグラフでも最短距離を求められるアルゴリズム。 めちゃめちゃ参考にしました: https://ei1333.github.io/library/graph/shortest-path/bellman-ford.hpp
vector<T> bellman_ford(const vector<Edge<T>>& edges, int N, int start)
ベルマンフォード法を行い、頂点startから各頂点vまでの最短距離が格納されたvector であるdistを返す。
start
v
vector
dist
dist[v]は、vが到達できない頂点のとき正の無限大が格納され、startからvまでの経路に負の閉路があったときは負の無限大が格納される。
dist[v]
無限大と書いたが、実際には型Tで表せる最大/最小の数が使われている。
T
頂点数を $V$、辺の数を$E$として
#ifndef HARUILIB_GRAPH_BELLMANFORD_HPP #define HARUILIB_GRAPH_BELLMANFORD_HPP #include <cassert> #include <queue> #include <vector> #include <limits> #include "graph/graph_template.hpp" // 完全にパクリました // https://ei1333.github.io/library/graph/shortest-path/bellman-ford.hpp template <typename T> std::vector<T> bellman_ford(const std::vector<Edge<T>>& edges, int N, int start) { assert(0 <= start && start < N); const int M = int(edges.size()); constexpr T PLINF = std::numeric_limits<T>::max(); constexpr T MNINF = std::numeric_limits<T>::min(); std::vector<T> dist(N, PLINF); dist[start] = T(0); for (int i=0; i<N-1; i++) { for (int j=0; j<M; j++) { Edge e = edges[j]; if (dist[e.from] >= PLINF) continue; if (dist[e.to] > dist[e.from] + e.cost) { dist[e.to] = dist[e.from] + e.cost; } } } std::vector<bool> negative(N, false); for (int i=0; i<N; i++) { for (int j=0; j<M; j++) { Edge e = edges[j]; if (dist[e.from] >= PLINF) continue; if (dist[e.to] > dist[e.from] + e.cost) { dist[e.to] = dist[e.from] + e.cost; negative[e.to] = true; } if (negative[e.from]) negative[e.to] = true; } } for (int i=0; i<N; i++) if (negative[i]) dist[i] = MNINF; return dist; } #endif // HARUILIB_GRAPH_BELLMANFORD_HPP
#line 1 "graph/bellmanford.hpp" #include <cassert> #include <queue> #include <vector> #include <limits> #line 1 "graph/graph_template.hpp" #line 5 "graph/graph_template.hpp" template <typename T> struct Edge { int from; int to; T cost; // default constructor Edge () : from(-1), to(-1), cost(T(0)) {} Edge(int _from, int _to, T _cost) : from(_from), to(_to), cost(_cost) {} // unweighted Edge(int _from, int _to) : from(_from), to(_to), cost(T(1)) {} bool operator==(const Edge& rhs) const { return from == rhs.from && to == rhs.to && cost == rhs.cost; } bool operator<(const Edge& rhs) const { return cost < rhs.cost; } bool operator>(const Edge& rhs) const { return cost > rhs.cost; } }; template <typename T> struct Graph : std::vector<std::vector<Edge<T>>> { using std::vector<std::vector<Edge<T>>>::vector; // inherit constructors void add_edge(int i, Edge<T> e) { (*this)[i].push_back(e); } void add_edge(Edge<T> e) { (*this)[e.from].push_back(e); } // weighted void add_edge(int _from, int _to, T _cost) { (*this)[_from].push_back(Edge(_from, _to, _cost)); } // unweighted void add_edge(int _from, int _to) { (*this)[_from].push_back(Edge(_from, _to, T(1))); } }; #line 10 "graph/bellmanford.hpp" // 完全にパクリました // https://ei1333.github.io/library/graph/shortest-path/bellman-ford.hpp template <typename T> std::vector<T> bellman_ford(const std::vector<Edge<T>>& edges, int N, int start) { assert(0 <= start && start < N); const int M = int(edges.size()); constexpr T PLINF = std::numeric_limits<T>::max(); constexpr T MNINF = std::numeric_limits<T>::min(); std::vector<T> dist(N, PLINF); dist[start] = T(0); for (int i=0; i<N-1; i++) { for (int j=0; j<M; j++) { Edge e = edges[j]; if (dist[e.from] >= PLINF) continue; if (dist[e.to] > dist[e.from] + e.cost) { dist[e.to] = dist[e.from] + e.cost; } } } std::vector<bool> negative(N, false); for (int i=0; i<N; i++) { for (int j=0; j<M; j++) { Edge e = edges[j]; if (dist[e.from] >= PLINF) continue; if (dist[e.to] > dist[e.from] + e.cost) { dist[e.to] = dist[e.from] + e.cost; negative[e.to] = true; } if (negative[e.from]) negative[e.to] = true; } } for (int i=0; i<N; i++) if (negative[i]) dist[i] = MNINF; return dist; }