大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
Problem Description
在每年的校赛里，全部进入决赛的同学都会获得一件非常美丽的t-shirt。可是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以如今他们想要寻找最短的从商店到赛场的路线，你能够帮助他们吗？
Input
输入包含多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包含3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员须要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
输入保证至少存在1条商店到赛场的路线。
Output
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间
Sample Input
2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0
Sample Output
3 2 代码：<pre name="code" class="cpp">#include<iostream> #include<cstdio> #include<cstring> #define maxx 99999999 #include<queue> using namespace std; struct node{ int to,w; int pre; //表示 同一起点的前一条边 }edge[20005]; int vis[505],dis[505]; int next[20005]; int m,n; int tot; void addedge(int u,int v,int w) { int j,t=0; for(j=next[u];j!=-1;j=edge[j].pre) //去重边 { if(v==edge[j].to&&w>=edge[j].w) { t=1; break; } } if(t==1) return; edge[tot].to=v; edge[tot].w=w; edge[tot].pre=next[u];// 邻接表的存储 next[u]=tot++; // edge[tot].to=u; //构造反向边 edge[tot].w=w; edge[tot].pre=next[v]; next[v]=tot++; return; } int spfa() { queue<int>q; int now; for(int i=1;i<=m;i++) { vis[i]=0; dis[i]=maxx; } dis[1]=0; vis[1]=1; q.push(1); while(!q.empty()) { now=q.front(); q.pop(); vis[now]=0; //反向边 for(int i=next[now];i!=-1;i=edge[i].pre) //遍历同一起点的全部边(从最后一条边開始) { int v=edge[i].to; if(dis[v]>dis[now]+edge[i].w) { dis[v]=dis[now]+edge[i].w; if(!vis[v]) { vis[v]=1; q.push(v); } } } } return dis[m]; } int main() { while(~scanf("%d%d",&m,&n)) { if(m==0&&n==0) break; tot=1; memset(next,-1,sizeof(next)); while(n--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); addedge(a,b,c); } int s=spfa(); cout<<s<<endl; } return 0; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/117984.html原文链接：https://javaforall.net
