1.给定一个带权有向图，用bellman-Ford来判定是否存在负权回路

输入

n m
1 2 3
4 5 6
...

其中n为图中顶点数，m为图中边数

输出

如果图中没有负权回路，就输出每个顶点的最短路径，如果有输出“有负权环”即可。

code

#include <bits/stdc++.h>
using namespace std;

int n,m;

const int N = 10010;
const int INF = 0x3f3f3f3f;

int dist[N],backup[N];

struct edge{
    int a,b,c;
}e[N];

void bellman_ford(){

    memset(dist,INF,sizeof(dist));

    dist[1] = 0;
    for(int i = 1; i <= n-1 ; i++){
        memcpy(backup,dist,sizeof(dist));
        for(int j = 1; j <= m; j++){
            edge ee = e[j];
            //下面这行核心代码易错
            dist[ee.b] = min(dist[ee.b],backup[ee.a]+ee.c);
        }
    }

    memcpy(backup,dist,sizeof(dist));
    for(int j = 1; j <= m; j++){
        edge ee = e[j];
        dist[ee.b] = min(dist[ee.b],backup[ee.a] + ee.c);
    }

    for(int i = 1; i <= n; i++){
        if(backup[i] != dist[i]){
            printf("从1到达%d的路径中存在负权回路\n",i);
            continue;
        }
        else printf("从1到达%d的最短路径为：%d\n",i,dist[i]);
    }

}


int main(){
    cin >> n >> m;
    for(int i = 1 ; i <= m; i++)
        cin >> e[i].a >> e[i].b >> e[i].c;
    bellman_ford();

    return 0;
}