1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 #include<vector> 6 #include<set> 7 #define CLR(a,b) memset((a),(b),sizeof((a))) 8 using namespace std; 9 10 const int N = 30001;11 const int M = 150001;12 const int inf = 0x3f3f3f3f;13 14 int n, m;15 bool s[N];16 int head[N];17 int cnt;18 struct edge{19     int nex;20     int v, w;21 }g[M];22 struct node{23     int v, w;24     node(int _v=0,int _w=0):v(_v),w(_w){}25     bool operator < (const node&r)const{26         return r.w < w;27     }28 };29 void add_edge(int u,int v,int w){30     g[cnt].v = v;31     g[cnt].w = w;32     g[cnt].nex = head[u];33     head[u] = cnt++;34 }35 void dij(){36     int i, u, v, w;37     node t;38     CLR(s, 0);39     priority_queue<node>q;40     q.push(node(1,0));41     while(!q.empty()){42         t = q.top(); q.pop();43         u = t.v;44         if(s[u]) continue;45         s[u] = 1;46         if(u == n) break;47         for(i = head[u]; ~i; i = g[i].nex){48             v = g[i].v;49             if(!s[v]){50                 w = t.w + g[i].w;51                 q.push(node(v, w));52             }53         }54     }55     printf("%d\n", t.w);56 }57 int main(){58     int i, j, a, b, c;59     scanf("%d %d", &n, &m);60     cnt = 0;61     CLR(head, -1);62     for(i = 1; i <= m; ++i){63         scanf("%d %d %d", &a, &b, &c);64         add_edge(a,b,c);65     }66     dij();67     return 0;68 }