CodeForces 20C

这题有一点坑，用d[N]int的话会上溢所以要用long long
 1 #include <iostream>
 2 #include <string.h>
 3 #include <queue>
 4 #include <vector>
 5 #include <utility>
 6 #include <cstdio>
 7 using namespace std;
 8 #define N 100005
 9 #define M 400005
10 typedef long long LL;
11 const LL inf = 1<<62;
12 LL v[M],w[M],next[M],first[N],d[N],e;
13 int f[N],o[N];
14 bool inq[N];
15 void addedge(int a,int b,int x){
16     v[e]=b;
17     w[e]=x;
18     next[e]=first[a];
19     first[a]=e++;
20 }
21 void SPFA(int st){
22     queue<int> q;
23     d[st]=0;
24     q.push(st);
25     inq[st]=1;
26     f[1]=-1;
27     while(!q.empty()){
28         int u = q.front();
29         q.pop();
30         inq[u] = 0;
31         for(int i=first[u];i!=-1;i=next[i]){
32             if(d[v[i]]>d[u]+w[i]){
33                 d[v[i]]=d[u]+w[i];
34                 f[v[i]]=u;
35                 if(!inq[v[i]]){
36                     q.push(v[i]);
37                     inq[v[i]]=1;
38                 }
39             }
40         }
41     }
42 }
43 int main(){
44     int n,m,a,b,x;
45    // freopen("test.txt","r",stdin);
46     while(cin>>n>>m){
47         e=0;
48         for(int i=0;i<=n;i++){
49             first[i]=-1;
50             inq[i]=false;
51             d[i]=inf;
52         }
53         for(int i=0;i<m;i++){
54             cin>>a>>b>>x;
55             addedge(a,b,x);
56             addedge(b,a,x);
57         }
58         SPFA(1);
59         if(d[n]==inf)cout<<"-1"<<endl;
60         else {
61             int r=0;
62             for(int i=f[n];i!=-1;i=f[i]){
63                 o[r]=i;
64                 r++;
65             }
66             for(int i=r;i>0;i--){
67                 printf("%d ",o[i-1]);
68             }
69             printf("%d
",n);
70         }
71     }
72     return 0;
73 }