SPFA ：求一个点到其他所有点的最短路，时间快。队列处理，队头元素所有相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。直到队列为空时算法结束。
例题 hdu 2680
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define M 1009 4 #define INF 0x3f3f3f3f 5 struct edge 6 { 7 int to,w;//保存边的信息，包括边的终点和权值 8 }; 9 int dis[M]; //最短距离 10 bool vis[M]; //标记该点是否在队列 11 vector<edge> g[M]; //利用一个vector保存，g[i]表示以i为起点的所有边的信息 12 int n,m,ee; 13 void spfa(int u) 14 { 15 for(int i = 0;i <= n;i++) //初始化 16 { 17 dis[i] = INF; 18 vis[i] = false; 19 } 20 dis[u] = 0; 21 vis[u] = true; //加入队列,标记 22 queue<int> q; 23 q.push(u); 24 while(!q.empty()) 25 { 26 u = q.front(); 27 vis[u] = false; 28 q.pop(); 29 for(int i = 0;i < g[u].size();i++) 30 { 31 int v = g[u][i].to; //找出这条边的终点 32 int w = g[u][i].w; //边的权值 33 if(dis[v] > dis[u]+w) //如果终点的最短距离比起点的最短距离加上这条边的权值那么就更新 34 { 35 dis[v] = dis[u]+w; 36 if(!vis[v]) //如果v点的最短距离有所更新并且不在队列中，就将其加入队列。 37 { //否则就不需要重复加入队列增加不必要的操作。 38 vis[v] = true; //加入队列并标记 39 q.push(v); 40 } 41 } 42 } 43 } 44 } 45 int main() 46 { 47 while(scanf("%d %d %d",&n,&m,&ee)==3) 48 { 49 for(int i = 0;i <= n;i++) //vector进行清空 50 g[i].clear(); 51 for(int i = 0;i < m;i++) 52 { 53 int a,b,c; 54 scanf("%d %d %d",&a,&b,&c); 55 edge e; 56 e.to = b; 57 e.w = c; 58 g[a].push_back(e); 59 //e.to = a; 60 //g[b].push_back(e); 双边加上 61 int s; 62 scanf("%d",&s); 63 for(int i = 0;i < s;i++) 64 { 65 int a; 66 scanf("%d",&a); 67 edge e; 68 e.to = a; 69 e.w = 0; 70 g[0].push_back(e); //将家里到起点的权值设为0 71 //e.to = 0; 72 //g[a].push_back(e); //从起点到家里是否有路其实无关紧要，因为思考一下有路的话 起点到起点也是0，所以根本不影响结果 73 } 74 spfa(0); 75 if(dis[ee]==INF) 76 printf("-1 "); 77 else 78 printf("%d ",dis[ee]); 79 } 80 return 0; 81 }