tzoj5779 最短路（SPFA模板）

时间限制(普通/Java):1000MS/3000MS 内存限制:65536KByte

描述

给定 M 条边， N 个点的带权无向图。求 1到 N 的最短路。

输入

第一行：N,M(N≤100000，M≤500000)；

接下来M行3个正整数：ai,bi,ci表示ai,bi之间有一条长度为ci的路，ci≤1000。

输出

一个整数，表示 1 到 N 的最短距离。

样例输入

4 4
1 2 1
2 3 1
3 4 1
2 4 1

样例输出

提示

注意图中可能有重边和自环，数据保证 1 到 N 有路径相连。

SPFA算法原理参考

算法优点：

1.时间复杂度比普通的Dijkstra和Ford低

2.能够计算负权图问题

3.能够判断是否有负环 (即：每跑一圈，路径会减小，所以会一直循环跑下去)

 1 #include <cstdio>
 2 #include <vector>
 3 #include <queue>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int N=1e5+5,INF=0x3f3f3f3f;
 8 struct Node{
 9     int to,d;
10 };
11 int dst[N],vis[N];
12 vector<Node> g[N];
13 
14 void SPFA(int u){
15     queue<int> que;
16     memset(vis,0,sizeof vis);
17     memset(dst,INF,sizeof dst);
18     dst[u]=0,vis[u]=1;
19     que.push(u);
20     while(!que.empty()){
21         int f=que.front();
22         que.pop();
23         vis[f]=0;
24         int len=g[f].size();
25         for(int i=0;i<len;i++){
26             Node v=g[f][i];
27             if(v.d+dst[f]<dst[v.to]){
28                 dst[v.to]=v.d+dst[f];
29                 if(vis[v.to]==0){
30                     que.push(v.to);
31                     vis[v.to]=1;
32                 }
33             }
34         }
35     }
36 }
37 
38 int main(){
39     int n,m,a,b,c;
40     Node node;
41     scanf("%d%d",&n,&m);
42     while(m--){
43         scanf("%d%d%d",&a,&b,&c);
44         node.to=b,node.d=c;
45         g[a].push_back(node);
46         node.to=a,node.d=c;
47         g[b].push_back(node);
48     }
49     SPFA(1);
50     printf("%d
",dst[n]);
51 }