shortest-path/bfs01.hpp
Depends on
Verified with
Code
#pragma once
#include "../graph/graph-template.hpp"
// unreachable -> -1
template <typename T>
vector<T> bfs01(WeightedGraph<T>& g, int start = 0) {
int N = (int)g.size();
vector<T> d(N, -1);
vector<int> vis(N, 0);
deque<int> Q;
d[start] = 0;
Q.push_back(start);
while (!Q.empty()) {
int cur = Q.front();
Q.pop_front();
if (vis[cur]) continue;
vis[cur] = 1;
for (auto& dst : g[cur]) {
if (d[dst] != -1 and d[dst] <= d[cur] + dst.cost) continue;
d[dst] = d[cur] + dst.cost;
if (dst.cost == 0) {
Q.push_front(dst);
} else {
Q.push_back(dst);
}
}
}
return d;
}
#line 2 "shortest-path/bfs01.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([[maybe_unused]] 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 4 "shortest-path/bfs01.hpp"
// unreachable -> -1
template <typename T>
vector<T> bfs01(WeightedGraph<T>& g, int start = 0) {
int N = (int)g.size();
vector<T> d(N, -1);
vector<int> vis(N, 0);
deque<int> Q;
d[start] = 0;
Q.push_back(start);
while (!Q.empty()) {
int cur = Q.front();
Q.pop_front();
if (vis[cur]) continue;
vis[cur] = 1;
for (auto& dst : g[cur]) {
if (d[dst] != -1 and d[dst] <= d[cur] + dst.cost) continue;
d[dst] = d[cur] + dst.cost;
if (dst.cost == 0) {
Q.push_front(dst);
} else {
Q.push_back(dst);
}
}
}
return d;
}
Back to top page