boolBellman_Ford() { memset(dist, 0x3f, sizeof dist); for (int k = 1; k < n; k ++) for (int ver = 1; ver <= n; ver ++) for (int i = h[ver]; ~i; i = ne[i]) { int to = e[i]; if (dist[to] > dist[ver] + w[i]) dist[to] = dist[ver] + w[i]; }
for (int ver = 1; ver <= n; ver ++) for (int i = h[ver]; ~i; i = ne[i]) { int to = e[i]; if (dist[to] > dist[ver] + w[i]) returnfalse; } returntrue; }
SPFA求最短路
时间复杂度:O(E×V)
vector 存图
1 2 3 4 5 6 7
structEdge { int u, w; }; vector<Edge> g[N]; int dist[N], n, m; bitset<N> vis;