1A.
// // main.cpp // Richard // // Created by 邵金杰 on 16/8/14. // Copyright © 2016年 邵金杰. All rights reserved. // #include<iostream> #include<cstdio> #include<queue> #include<vector> using namespace std; struct edge{ int e,w; edge(int e,int w): e(e),w(w) {} }; const int INF=(1<<30); const int maxn=1000+10; int dist[maxn]; int T,N; vector<edge> edges[maxn]; void spfa() { for(int i=1;i<=N;i++) dist[i]=INF; dist[1]=0; queue<int> q; q.push(1); while(!q.empty()) { int s=q.front(); q.pop(); for(int i=0;i<edges[s].size();i++) { int e=edges[s][i].e; if(dist[s]+edges[s][i].w<dist[e]) { dist[e]=dist[s]+edges[s][i].w; q.push(edges[s][i].e); } } } printf("%d\n",dist[N]); } int main() { scanf("%d%d",&T,&N); int s,e,w; for(int i=0;i<T;i++) { scanf("%d%d%d",&s,&e,&w); edges[s].push_back(edge(e,w)); edges[e].push_back(edge(s,w)); } spfa(); return 0; }