最短路模板 —— Bellman_Ford

时间复杂度对比：
Dijkstra：$O(n^2)$
Dijkstra + 优先队列（堆优化）：$O(2?E+V?logV)$
SPFA：$O(k?E)$，$k$为每个节点进入队列的次数，一般小于等于$2$，最坏情况为$O(V?E)$
BellmanFord： $O(V?E)$，可检测负圈
Floyd： $O(n^3)$，计算每对节点之间的最短路径

结论:

$①$当权值为非负时，用Dijkstra。
$②$当权值有负值，且没有负圈，则用SPFA，SPFA能检测负圈，但是不能输出负圈。
$③$当权值有负值，而且可能存在负圈，则用BellmanFord，能够检测并输出负圈。
$④$SPFA检测负环：当存在一个点入队大于等于V次时，则有负环。

$PS$：优先队列和SPFA都有可能被题目卡数据$......$

Bellman_Ford：

#include<bits/stdc++.h>
using namespace std;const int MAX = 0x3f3f3f3f;
const int N = 1010;
int n, m, st; //点，边，起点typedef struct Edge { //边int u, v;int w;
} Edge;Edge edge[N];
int dis[N], pre[N];bool Bellman_Ford() {for(int i=1; i<=n; ++i) //初始化dis[i] = (i == st ? 0 : MAX);for(int i=1; i<=n-1; ++i){bool flag = false;for(int j = 1; j <= m; ++j)if(dis[edge[j].v] > dis[edge[j].u] + edge[j].w) { //松弛（顺序一定不能反~）dis[edge[j].v] = dis[edge[j].u] + edge[j].w;pre[edge[j].v] = edge[j].u;flag = true;}if(!flag) return true;//没有负环回路}bool flag = 1; //判断是否含有负权回路for(int i=1; i<=m; ++i)if(dis[edge[i].v] > dis[edge[i].u] + edge[i].w) {flag = 0;break;}return flag;
}void print_path(int end) { //打印最短路的路径stack <int> path;int now = end;while(1) { //前驱path.push(now);if(now == st) break;now = pre[now];}while(!path.empty()) {now = path.top();path.pop();if(path.empty()) printf("%d\n", now);else printf("%d-->", now);}
}int main() {scanf("%d%d%d", &n, &m, &st);pre[st] = st;for(int i=1; i<=m; ++i)scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);if(Bellman_Ford())for(int i = 1; i <= n; ++i) { //每个点最短路printf("%d\n", dis[i]);printf("Path:");print_path(i);}else printf("have circle!\n");
}