Bellman-Ford 求含负权最短路

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 #include <stdlib.h>
 5 #include <iostream>
 6 #include <sstream>
 7 #include <algorithm>
 8 #include <string>
 9 #include <queue>
10 #include <ctime>
11 #include <vector>
12 using namespace std;
13 const int maxn= 1e3+5;
14 const int maxm= 1e3+5;
15 const int inf = 0x3f3f3f3f;
16 typedef long long ll;
17 int n,m,s;   //n m s 分别表示 点数-标号从1开始 边数-标号从0开始 起点
18 struct edge
19 {
20     int u,v,w;    //u为边的起点 v为边的终点 w为边的权值
21 }edges[maxm];
22 int d[maxn];   //d[i]表示 i 点到源点 s 的最短距离
23 int p[maxn];    //p[i]记录最短路到达 i 之前的节点
24 int Bellman_Ford(int x)
25 {
26     for(int i=1;i<=n;i++)
27         d[i]=inf;
28     d[x]=0;
29     for(int i=1;i<n;i++)                //  n-1次迭代
30         for(int j=0;j<m;j++)            //  检查每条边
31         {
32             if(d[edges[j].u]+edges[j].w<d[edges[j].v])    // 松弛操作
33             {
34                 d[edges[j].v]=d[edges[j].u]+edges[j].w;
35                 p[edges[j].v]=edges[j].u;           //记录路径
36             }
37         }
38     int flag=1;
39     for(int i=0;i<m;i++)                       //判断是否有负环
40         if(d[edges[i].u]+edges[i].w<d[edges[i].v])
41         {
42             flag=0;
43             break;
44         }
45     return flag;            //返回最短路是否存在
46 }
47 void Print_Path(int x)
48 {
49     while(x!=p[x])          //逆序输出 正序的话用栈处理一下就好了
50     {
51         printf("%d ",x);
52         x=p[x];
53     }
54     printf("%d\n",x);
55 }
56 int main()
57 {
58     while(scanf("%d %d %d",&n,&m,&s)!=EOF)
59     {
60         for(int i=0;i<m;i++)
61             scanf("%d %d %d",&edges[i].u,&edges[i].v,&edges[i].w);
62         p[s]=s;
63         if(Bellman_Ford(s)==1)
64             for(int i=1;i<=n;i++)
65             {
66                 printf("%d %d\n",i,d[i]);
67                 Print_Path(i);
68             }
69         else
70             printf("sorry\n");
71         return 0;
72     }
73 }