SPFA

最坏情况下时间复杂度：O(nm)

一般情况下时间复杂度优于Bellman Ford

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string.h>
 4 #include<cstdio>
 5 #include<queue>
 6 using namespace std;
 7 struct edge
 8 {
 9     int to;
10     int weight;
11     int next;
12 }e[2002*2002*4];
13 int head[3003];
14 int dis[3003];
15 int vis[3003];
16 int cnt[3003];
17 int n,m;
18 int tot;
19 bool spfa(int s)
20 {
21     queue<int> q;
22     memset(dis,0x3f3f3f3f,sizeof(dis));
23     memset(vis,0,sizeof(vis));
24     memset(cnt,0,sizeof(cnt));
25     dis[s]=0;
26     vis[s]=1;
27     q.push(s);
28     while(!q.empty())
29     {
30         int u=q.front();
31         q.pop();
32         vis[u]=0;
33         for(int i=head[u];i;i=e[i].next)
34         {
35             int to=e[i].to;
36             if(dis[u]<0x3f3f3f3f&&dis[to]>dis[u]+e[i].weight)
37             {
38                 dis[to]=dis[u]+e[i].weight;
39                 if(!vis[to])
40                 {
41                     q.push(to);
42                     vis[to]=1;
43                     if(++cnt[to]>n)
44                     return 0;
45                 }
46             }
47         }
48     }
49     return 1;
50 }
51 void add(int x,int y,int z)
52 {
53     tot++;
54     e[tot].to=y;
55     e[tot].weight=z;
56     e[tot].next=head[x];
57     head[x]=tot;
58 }
59 int main()
60 {
61     cin>>n>>m;
62     for(int i=1;i<=m;i++)
63     {
64         int x,y,z;
65         cin>>x>>y>>z;
66         add(x,y,z);
67         add(y,x,z);
68     }
69     spfa(1);
70     cout<<dis[n]<<endl;
71     return 0;
72 }