SPFA

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<queue>
 6 using namespace std;
 7 const int MAX_V = 1100;
 8 const int MAX_E = 110000;
 9 const int INF = 0x3f3f3f3f;
10 
11 struct ENode
12 {
13     int to;
14     int w;
15     int Next;
16 };
17 ENode edegs[MAX_E];
18 int Head[MAX_V], tnt;
19 void Add_ENode (int a, int b, int w)
20 {
21     ++ tnt;
22     edegs[tnt].to= b;
23     edegs[tnt].w= w;
24     edegs[tnt].Next= Head[a];
25     Head[a]= tnt;
26     ++ tnt;
27     edegs[tnt].to= a;
28     edegs[tnt].w= w;
29     edegs[tnt].Next= Head[b];
30     Head[b]= tnt;
31 }
32 
33 int Dis[MAX_V];
34 bool visit[MAX_V]; //是否已经遍历过;
35 int que[MAX_V]; // 模拟队列;
36 int outque[MAX_V]; //记录每个点出队列的次数，防止有负边，保证无负边的图可以省略;
37 bool SPFA(int s, int n)
38 {
39     /*s：起点； n：点的总数*/
40     int iq; //队列中元素个数;
41     memset(Dis, INF, sizeof(Dis));
42     memset(visit, false, sizeof(visit));
43     memset(outque, 0, sizeof(outque));
44     iq= 0;
45     que[iq ++]= s;
46     visit[s]= true;
47     Dis[s]= 0;
48     int i= 0;
49     while (i< iq)
50     {
51         int u= que[i];
52         visit[u]= false;
53         outque[u] ++;
54         if (outque[u]> n) return false; //当一个点进出队列超过n 次，必然有负边存在;
55 
56         for (int k= Head[u]; k!= -1; k= edegs[k].Next)
57         {
58             /*bfs,和Dijkstra相似*/
59             int v= edegs[k].to;
60             if (Dis[v]> Dis[u]+ edegs[k].w)
61             {
62                 Dis[v]= Dis[u]+ edegs[k].w;
63                 if (! visit[v])
64                 {
65                     visit[v]= true;
66                     que[iq ++]= v;
67                 }
68             }
69         }
70         i ++;
71     }
72     return true;
73 }
74 
75 void into()
76 {
77     /**初始化*/
78     memset(Head,-1,sizeof(Head));
79     tnt= -1;
80 }
81 
82 int main()
83 {
84     int n, m;
85     int a, b, w;
86     while (~ scanf("%d %d", &n, &m))
87     {
88         into();
89         for (int i= 0; i< m; i ++)
90         {
91             scanf("%d %d %d", &a, &b, &w);
92             Add_ENode(a, b, w);
93         }
94         SPFA(1, n);
95         printf("%d
", Dis[n]);
96     }
97     return 0;
98 }
View Code