Bellman-Ford负权值最短路模版 – 谢民皆的个人分享

1.n个点，m条边，含有负边。
2.外层循环n-1次，内层循环m次，进行松弛
3.添加check变量判断本轮是否进行松弛了，如果未进行松弛则可以提前退出循环
4.处理有向边时，注意u[i]和v[i]的顺序不要颠倒

#include <iostream>
using namespace std;
int main() {
    int dis[20001] = {0}, u[200001], v[200001],w[200001]
    int n, m, inf = 99999999;
    fill(dis+2,dis+20001,inf);
    scanf("%d %d", &n, &m);
    for(int i = 1;  i <= m; i++){
        scanf("%d %d %d",&u[i], &v[i], &w[i]);
    }
    for(int k = 1; k <= n - 1; k++){
        int  check = 0;
        for(int i = 1; i <= m; i++){
            if(dis[v[i]] > dis[u[i]] + w[i]){
                dis[v[i]] = dis[u[i]] + w[i];
                check = 1;
            }
        }
        if(check == 0) break;
    }
    for(int i = 2; i <= n; i++){
        printf("%d\n",dis[i]);
    }
}

#include <iostream>

using namespace std;

int main() {

int dis[20001] = {0}, u[200001], v[200001],w[200001]

int n, m, inf = 99999999;

fill(dis+2,dis+20001,inf);

scanf("%d %d", &n, &m);

for(int i = 1; i <= m; i++){

scanf("%d %d %d",&u[i], &v[i], &w[i]);

}

for(int k = 1; k <= n - 1; k++){

int check = 0;

for(int i = 1; i <= m; i++){

if(dis[v[i]] > dis[u[i]] + w[i]){

dis[v[i]] = dis[u[i]] + w[i];

check = 1;

}

if(check == 0) break;

}

for(int i = 2; i <= n; i++){

printf("%d\n",dis[i]);

}