带负边权的最短路径（有向图）——Bellman-Ford算法

#include <iostream>
#include <cstring>
#include <cstdio>

#define MAX 100
#define INF 0x3f3f3f
using namespace std;
//有向图
struct Edge
{
    int u,v,cost;
}e[MAX];
int dist[MAX];  //最短路径
int prev[MAX];  //路径
int m,n;    //边数和顶点数

bool Bellman_Ford(int v0)
{
    int u=v0;
    for(int i=1;i<=n;i++)
        dist[i]=INF;
    dist[u]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++)
            if(dist[e[j].v]>dist[e[j].u]+e[j].cost)
            {
                dist[e[j].v]=dist[e[j].u]+e[j].cost;
                prev[e[j].v]=e[j].u;
            }
    for(int i=0;i<m;i++)
        if(dist[e[i].v]>dist[e[i].u]+e[i].cost)
            return 0;
    return 1;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
        cin>>e[i].u>>e[i].v>>e[i].cost;
    if(Bellman_Ford(1))
        for(int i = 1; i <= n; ++i) //每个点最短路
        {
            printf("%d\n", dist[i]);
        }
    else
        printf("have negative circle\n");
    return 0;
}
————————————————
版权声明：本文为CSDN博主「weixin_43249938」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_43249938/article/details/88217729

样例输入：
1
10 15
4 7 10
7 6 3
5 3 3
1 4 11
0 6 20
9 8 25
3 0 9
1 2 15
9 0 27
5 2 0
7 3 -5
1 7 21
5 0 1
9 3 16
1 8 4
4 1
0 3
6 9
2 1
8 7
0 4

样例输出：
-11
-9
-45
-15
17
7

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 
 5 #define MAX 900
 6 #define INF 0x3f3f3f
 7 using namespace std;
 8 struct Edge
 9 {
10     int u,v,cost;
11 }e[MAX];
12 int dist[MAX];  //最短路径
13 int m,n;    //边数和顶点数
14 
15 bool Bellman_Ford(int v0)
16 {
17     int u=v0;
18     for(int i=1;i<=n;i++)
19         dist[i]=INF;
20     dist[u]=0;
21     for(int i=1;i<=n;i++)
22         for(int j=0;j<m;j++)
23             if(dist[e[j].v]>dist[e[j].u]+e[j].cost)
24             {
25                 dist[e[j].v]=dist[e[j].u]+e[j].cost;
26             }
27     for(int i=0;i<m;i++)
28         if(dist[e[i].v]>dist[e[i].u]+e[i].cost)
29             return 0;
30     return 1;
31 }
32 
33 int main()
34 {    int T;
35     cin >> T; 
36     while(T--){
37         cin>>n>>m;
38         for(int i=0;i<m;i++){
39             int a,b,c;
40             cin >> a >> b >> c;
41             e[i].u = a+1;
42             e[i].v = b+1;
43             e[i].cost = c;
44         }
45         for(int i = 0 ; i < 6; i++){
46             int t1, t2;
47             cin >> t1 >> t2;
48             t1++;
49             t2++;
50             Bellman_Ford(t2);
51             int res = -dist[t1];
52             cout << res << endl;
53             e[m].u = t1;
54             e[m].v = t2;
55             e[m].cost = res;
56             m++;
57         }
58        
59     }
60     
61 
62     return 0;
63 }