hihocoder1093最短路（SPFA算法）

算法描述：

首先将起始节点入队，然后每次从队列中取出一个节点，更新其邻接点的最短路径值，若有被更新，则检查该邻接点是否在队列中，若不在队列中，则入队。如此循环直到队空时算法结束。

当图中不存在负环时，算法一定会收敛，并能得到所求最短路。原因在于，每次从队列中取出一个节点并更新其邻接点的过程其实都是在向最优解逼近的过程，且只有当有更新的时候才可能向队列增加节点。由于不断的在向最优解逼近，所以到最后一定会达到最优解且不再有节点入队，队列最终为空，算法收敛。SPFA算法与dijkstra相比有一个好处：dijkstra算法不能处理图中有负圈的情况，而在SPFA算法中，只需要记录每个节点入队的次数，若某个节点入队的次数超过了节点总数，那么可判定图中一定存在负圈。

SPFA算法对边数的依赖很强，因此，在实际应用中性能并不是很稳定（相对于dijkstra而言），但是对于稀疏图（边比较少）的情况，SPFA比较优越。

我的代码：

 1 #include <iostream>
 2 #include <queue>
 3 #include <vector>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 #define MAXN 100005
 9 #define INF 0x7fffffff
10 
11 struct edge
12 {
13     int y, w;
14     edge(int _y, int _w):y(_y),w(_w){}
15 };
16 
17 vector<edge> v[MAXN];
18 int d[MAXN], n, m, s, t;
19 bool inq[MAXN];
20 
21 void spfa()
22 {
23     for(int i=1; i<=n; ++i) d[i] = INF;
24     d[s] = 0;
25     memset(inq+1, 0, n);
26     queue<int> q;
27     q.push(s);
28     inq[s] = true;
29     while(!q.empty())
30     {
31         int x = q.front();
32         q.pop();
33         inq[x] = false;
34         int sz = v[x].size();
35         for(int i=0; i<sz; ++i)
36         {
37             int y = v[x][i].y, w = v[x][i].w;
38             if(d[y]>d[x]+w)
39             {
40                 d[y] = d[x]+w;
41                 if(!inq[y]) q.push(y);
42             }
43         }
44     }
45 }
46 
47 int main()
48 {
49     while(cin>>n>>m>>s>>t)
50     {
51         for(int i=1; i<=n; ++i) v[i].clear();
52         while(m--)
53         {
54             int x, y, w;
55             cin>>x>>y>>w;
56             v[x].push_back(edge(y, w));
57             v[y].push_back(edge(x, w));
58         }
59         spfa();
60         cout<<d[t]<<endl;
61     }
62     return 0;
63 }

题目链接：http://hihocoder.com/problemset/problem/1093