#include<queue> #include<vector> #include<cstring> using namespace std; const int Max=2100000; typedef pair<int,int> Pair; priority_queue<Pair,vector<Pair>,greater<Pair> > Q; int n,tail,dis[200],head[200]; struct data { int w,to,next; }k,edge[21000]; void (int u,int v,int x) { edge[tail].w=x; edge[tail].to=v; edge[tail].next=head[u]; head[u]=tail++; } void Dij() { Pair s,u; int v,val; dis[1]=0; s.first=0; s.second=1; Q.push(s); while (!Q.empty()) { u=Q.top(); Q.pop(); v=u.second; val=u.first; if (dis[v]<val) continue; for (int i=head[v];i!=-1;i=edge[i].next) { k=edge[i]; if (dis[k.to]>dis[v]+k.w) { dis[k.to]=dis[v]+k.w; Q.push(Pair(dis[k.to],k.to)); } } } } int main() { int n,m,u,v,x; while (scanf("%d%d",&n,&m)!=EOF) { if (!n && !m) break; tail=0; for (int i=0;i<200;i++) head[i]=-1; for (int i=0;i<200;i++) dis[i]=Max; for (int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&x); build(u,v,x); build(v,u,x); } Dij(); printf("%dn",dis[n]); } return 0; }
|
近期评论