This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dgcnz/cp-library
#include "cplib/graph/spfa.hpp"
#ifndef CPLIB_SPFA_HPP #define CPLIB_SPFA_HPP #include "cplib/graph/graph.hpp" #include <limits> #include <queue> namespace cplib { using namespace std; template <typename W, W INF = numeric_limits<W>::max()> struct SPFA { Graph<W> const &g; vector<W> dist; SPFA(Graph<W> const &g) : g(g) {} bool operator()(int s) { int n = g.size(); dist.assign(n, INF); vector<int> cnt(n, 0); vector<bool> inqueue(n, false); queue<int> q; dist[s] = 0; q.push(s); inqueue[s] = true; while (!q.empty()) { int v = q.front(); q.pop(); inqueue[v] = false; for (auto edge : g[v]) { int to = edge.first; int len = edge.second; if (dist[v] + len < dist[to]) { dist[to] = dist[v] + len; if (!inqueue[to]) { q.push(to); inqueue[to] = true; cnt[to]++; if (cnt[to] > n) return false; // negative cycle } } } } return true; } }; } // namespace cplib #endif // CPLIB_SPFA_HPP
#line 1 "cplib/graph/spfa.hpp" #line 1 "cplib/graph/graph.hpp" #include <algorithm> #include <cassert> #include <utility> #include <vector> namespace cplib { using namespace std; template <typename W> struct Graph { using adj_list = vector<pair<int, W>>; vector<adj_list> g; Graph(int n = 0) : g(n) {} size_t size() const { return g.size(); } int vertex(pair<int, W> e) const { return e.first; } void add_edge(int u, int v) { g[u].emplace_back(v, W()); } void add_edge(int u, int v, W weights) { g[u].emplace_back(v, weights); } void add_undirected_edge(int u, int v) { g[u].emplace_back(v, W()); g[v].emplace_back(u, W()); } void add_undirected_edge(int u, int v, W weights) { g[u].emplace_back(v, weights); g[v].emplace_back(u, weights); } int add_node(void) { g.push_back({}); return g.size() - 1; } adj_list &operator[](int u) { return g[u]; } adj_list operator[](int u) const { return g[u]; } typename vector<adj_list>::iterator begin() { return g.begin(); }; typename vector<adj_list>::iterator end() { return g.end(); } typename vector<adj_list>::const_iterator begin() const { return g.begin(); }; typename vector<adj_list>::const_iterator end() const { return g.end(); } }; template <> struct Graph<void> { using adj_list = vector<int>; vector<adj_list> g; Graph(int n = 0) : g(n) {} size_t size() const { return g.size(); } int vertex(int e) const { return e; } void add_edge(int u, int v) { g[u].emplace_back(v); } void add_undirected_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); } int add_node(void) { g.push_back({}); return g.size() - 1; } adj_list &operator[](int u) { return g[u]; } adj_list operator[](int u) const { return g[u]; } typename vector<adj_list>::iterator begin() { return g.begin(); }; typename vector<adj_list>::iterator end() { return g.end(); } typename vector<adj_list>::const_iterator begin() const { return g.begin(); }; typename vector<adj_list>::const_iterator end() const { return g.end(); } }; using UndirectedGraph = Graph<void>; } // namespace cplib #line 5 "cplib/graph/spfa.hpp" #include <limits> #include <queue> namespace cplib { using namespace std; template <typename W, W INF = numeric_limits<W>::max()> struct SPFA { Graph<W> const &g; vector<W> dist; SPFA(Graph<W> const &g) : g(g) {} bool operator()(int s) { int n = g.size(); dist.assign(n, INF); vector<int> cnt(n, 0); vector<bool> inqueue(n, false); queue<int> q; dist[s] = 0; q.push(s); inqueue[s] = true; while (!q.empty()) { int v = q.front(); q.pop(); inqueue[v] = false; for (auto edge : g[v]) { int to = edge.first; int len = edge.second; if (dist[v] + len < dist[to]) { dist[to] = dist[v] + len; if (!inqueue[to]) { q.push(to); inqueue[to] = true; cnt[to]++; if (cnt[to] > n) return false; // negative cycle } } } } return true; } }; } // namespace cplib