This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
/***** ベルマンフォード法 *****/
// 計算量 O(|V| |E|)
// 単一始点最短路問題を解く。各辺の重みは負数でもよい
// 通常 |V| - 1 回実行してループを抜けるが、負のコストの閉路が存在する場合は
// V 回目でも更新が発生する → 負の閉路の検出にも使える
// グラフに、s から到達可能な負の閉路があるかどうかを検出する
template <typename T>
bool find_negative_loop(vector< vector< Edge<T> > > &G, int s) {
int V = G.size();
vector<T> d(V);
for(int i=0; i<V; i++) d[i] = numeric_limits<T>::max(); d[s] = 0;
for(int i=0; i<V; i++) {
for(int j=0; j<V; j++) {
for(int k=0; k<G[j].size(); k++) {
Edge<T> e = G[j][k];
if(d[j] != numeric_limits<T>::max() && d[e.to] > d[j] + e.cost) {
d[e.to] = d[j] + e.cost;
// n 回目にも更新があるなら負の閉路が存在する
if(i == V - 1) return true;
}
}
}
}
return false;
}
// グラフ全体を見て、負の閉路があるかどうかを検出する
template <typename T>
bool find_negative_loop_whole(vector< vector< Edge<T> > > &G) {
int V = G.size();
vector<T> d(V);
fill(d.begin(), d.end(), 0);
for(int i=0; i<V; i++) {
for(int j=0; j<V; j++) {
for(int k=0; k<G[j].size(); k++) {
Edge<T> e = G[j][k];
if(d[e.to] > d[j] + e.cost) {
d[e.to] = d[j] + e.cost;
// n 回目にも更新があるなら負の閉路が存在する
if(i == V - 1) return true;
}
}
}
}
return false;
}
// 頂点の数V, 辺の数Eのグラフにおいて、 s 番目の頂点から各頂点への最短距離を求める
template <typename T>
vector<T> bellman(vector< vector< Edge<T> > > &G, int s) {
// 頂点の数と辺の数を数える
int V = G.size();
vector<T> d(V);
for(int i=0; i<V; i++) d[i] = numeric_limits<T>::max();
d[s] = 0;
while(true) {
bool update = false;
for(int i=0; i<V; i++) {
for(int j=0; j<G[i].size(); j++) {
Edge<T> e = G[i][j];
if(d[i] != numeric_limits<T>::max() && d[e.to] > d[i] + e.cost) {
d[e.to] = d[i] + e.cost;
update = true;
}
}
}
if(!update) break;
}
return d;
}
#line 1 "graph/graph_001_bellman.cpp"
/***** ベルマンフォード法 *****/
// 計算量 O(|V| |E|)
// 単一始点最短路問題を解く。各辺の重みは負数でもよい
// 通常 |V| - 1 回実行してループを抜けるが、負のコストの閉路が存在する場合は
// V 回目でも更新が発生する → 負の閉路の検出にも使える
// グラフに、s から到達可能な負の閉路があるかどうかを検出する
template <typename T>
bool find_negative_loop(vector< vector< Edge<T> > > &G, int s) {
int V = G.size();
vector<T> d(V);
for(int i=0; i<V; i++) d[i] = numeric_limits<T>::max(); d[s] = 0;
for(int i=0; i<V; i++) {
for(int j=0; j<V; j++) {
for(int k=0; k<G[j].size(); k++) {
Edge<T> e = G[j][k];
if(d[j] != numeric_limits<T>::max() && d[e.to] > d[j] + e.cost) {
d[e.to] = d[j] + e.cost;
// n 回目にも更新があるなら負の閉路が存在する
if(i == V - 1) return true;
}
}
}
}
return false;
}
// グラフ全体を見て、負の閉路があるかどうかを検出する
template <typename T>
bool find_negative_loop_whole(vector< vector< Edge<T> > > &G) {
int V = G.size();
vector<T> d(V);
fill(d.begin(), d.end(), 0);
for(int i=0; i<V; i++) {
for(int j=0; j<V; j++) {
for(int k=0; k<G[j].size(); k++) {
Edge<T> e = G[j][k];
if(d[e.to] > d[j] + e.cost) {
d[e.to] = d[j] + e.cost;
// n 回目にも更新があるなら負の閉路が存在する
if(i == V - 1) return true;
}
}
}
}
return false;
}
// 頂点の数V, 辺の数Eのグラフにおいて、 s 番目の頂点から各頂点への最短距離を求める
template <typename T>
vector<T> bellman(vector< vector< Edge<T> > > &G, int s) {
// 頂点の数と辺の数を数える
int V = G.size();
vector<T> d(V);
for(int i=0; i<V; i++) d[i] = numeric_limits<T>::max();
d[s] = 0;
while(true) {
bool update = false;
for(int i=0; i<V; i++) {
for(int j=0; j<G[i].size(); j++) {
Edge<T> e = G[i][j];
if(d[i] != numeric_limits<T>::max() && d[e.to] > d[i] + e.cost) {
d[e.to] = d[i] + e.cost;
update = true;
}
}
}
if(!update) break;
}
return d;
}