shortest-path/bellman-ford.hpp
Depends on
Verified with
Code
#pragma once
#include "../graph/graph-template.hpp"
// bellman-ford法
// goalが存在しないとき-> 負閉路が存在するときは空列を返す
// goalが存在するとき -> startとgoalの間に負閉路が存在する時に負閉路を返す
template <typename T>
vector<T> bellman_ford(int N, Edges<T> &es, int start = 0, int goal = -1) {
T INF = numeric_limits<T>::max() / 2;
vector<T> d(N, INF);
d[start] = 0;
for (int i = 0; i < N; i++) {
bool update = false;
for (auto &e : es) {
if (d[e.src] == INF) continue;
if (d[e.to] > d[e.src] + e.cost) {
update = true, d[e.to] = d[e.src] + e.cost;
}
}
if (!update) return d;
}
if (goal == -1) return vector<T>();
vector<bool> negative(N, false);
for (int i = 0; i < N; i++) {
for (auto &e : es) {
if (d[e.src] == INF) continue;
if (d[e.to] > d[e.src] + e.cost)
negative[e.to] = true, d[e.to] = d[e.src] + e.cost;
if (negative[e.src] == true) negative[e.to] = true;
}
}
if (negative[goal] == true)
return vector<T>();
else
return d;
}
#line 2 "shortest-path/bellman-ford.hpp"
#line 2 "graph/graph-template.hpp"
template <typename T>
struct edge {
int src, to;
T cost;
edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}
edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}
edge &operator=(const int &x) {
to = x;
return *this;
}
operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnweightedGraph = vector<vector<int>>;
// Input of (Unweighted) Graph
UnweightedGraph graph(int N, int M = -1, bool is_directed = false,
bool is_1origin = true) {
UnweightedGraph g(N);
if (M == -1) M = N - 1;
for (int _ = 0; _ < M; _++) {
int x, y;
cin >> x >> y;
if (is_1origin) x--, y--;
g[x].push_back(y);
if (!is_directed) g[y].push_back(x);
}
return g;
}
// Input of Weighted Graph
template <typename T>
WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false,
bool is_1origin = true) {
WeightedGraph<T> g(N);
if (M == -1) M = N - 1;
for (int _ = 0; _ < M; _++) {
int x, y;
cin >> x >> y;
T c;
cin >> c;
if (is_1origin) x--, y--;
g[x].emplace_back(x, y, c);
if (!is_directed) g[y].emplace_back(y, x, c);
}
return g;
}
// Input of Edges
template <typename T>
Edges<T> esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) {
Edges<T> es;
for (int _ = 0; _ < M; _++) {
int x, y;
cin >> x >> y;
T c;
if (is_weighted)
cin >> c;
else
c = 1;
if (is_1origin) x--, y--;
es.emplace_back(x, y, c);
}
return es;
}
// Input of Adjacency Matrix
template <typename T>
vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true,
bool is_directed = false, bool is_1origin = true) {
vector<vector<T>> d(N, vector<T>(N, INF));
for (int _ = 0; _ < M; _++) {
int x, y;
cin >> x >> y;
T c;
if (is_weighted)
cin >> c;
else
c = 1;
if (is_1origin) x--, y--;
d[x][y] = c;
if (!is_directed) d[y][x] = c;
}
return d;
}
/**
* @brief グラフテンプレート
* @docs docs/graph/graph-template.md
*/
#line 6 "shortest-path/bellman-ford.hpp"
// bellman-ford法
// goalが存在しないとき-> 負閉路が存在するときは空列を返す
// goalが存在するとき -> startとgoalの間に負閉路が存在する時に負閉路を返す
template <typename T>
vector<T> bellman_ford(int N, Edges<T> &es, int start = 0, int goal = -1) {
T INF = numeric_limits<T>::max() / 2;
vector<T> d(N, INF);
d[start] = 0;
for (int i = 0; i < N; i++) {
bool update = false;
for (auto &e : es) {
if (d[e.src] == INF) continue;
if (d[e.to] > d[e.src] + e.cost) {
update = true, d[e.to] = d[e.src] + e.cost;
}
}
if (!update) return d;
}
if (goal == -1) return vector<T>();
vector<bool> negative(N, false);
for (int i = 0; i < N; i++) {
for (auto &e : es) {
if (d[e.src] == INF) continue;
if (d[e.to] > d[e.src] + e.cost)
negative[e.to] = true, d[e.to] = d[e.src] + e.cost;
if (negative[e.src] == true) negative[e.to] = true;
}
}
if (negative[goal] == true)
return vector<T>();
else
return d;
}
Back to top page