spfa【模板】

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 const int N=1000005,INF=0x3f3f3f3f;
 5 int n,m,cnt,x[N],y[N],z[N],H[N<<1],Q[N+10];
 6 long long Ans,Dist[N];
 7 bool vis[N];
 8 struct Edge
 9 {
10     int to,val,nxt;
11 }e[N<<1];
12 
13 void read(int &now)
14 {
15     now=0;char c=getchar();
16     while(c>‘9‘||c<‘0‘)c=getchar();
17     while(c>=‘0‘&&c<=‘9‘)now=(now<<3)+(now<<1)+c-‘0‘,c=getchar();
18 }
19 
20 void AddEdge(int u,int v,int w)
21 {
22     e[++cnt].to = v;
23     e[cnt].val = w;
24     e[cnt].nxt = H[u];
25     H[u] = cnt;
26 }
27 
28 void SPFA(int x)
29 {
30     memset(vis,0,sizeof vis);
31     memset(Dist,INF,sizeof Dist);
32     vis[x]=1;
33     Dist[x]=0;
34     int h=0,t=1;
35     Q[h]=1;
36     while(h<t)
37     {
38         int cur=Q[h++];
39         vis[cur]=0;
40         for(int i=H[cur];i;i=e[i].nxt)
41         {
42             int to=e[i].to,v=e[i].val;
43             if(Dist[to]>Dist[cur]+v)
44             {
45                 Dist[to]=Dist[cur]+v;
46                 if(!vis[to])
47                   Q[t++]=to,vis[to]=1;
48             }
49         }
50     }
51 }
52 
53 int main()
54 {
55     read(n);read(m);
56     for(int i=1;i<=m;++i)
57       read(x[i]),read(y[i]),read(z[i]),AddEdge(x[i],y[i],z[i]);
58     SPFA(1);
59     return 0;
60 }