Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 20910 Accepted Submission(s): 8939
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条商店到赛场的路线。
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
Source UESTC 6th Programming Contest Online
Recommend lcy
#define DeBUG#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <algorithm>#include <vector>#include <stack>#include <queue>#include<cassert>#include<set>
#ifdef DeBUG#define bug assert#else#define bug //#endif#define INF 10000000using namespace std ;int main(){ #ifdef DeBUG freopen("C:\\Users\\Sky\\Desktop\\1.in","r",stdin); #endif const int start=1; int end; int road[105][105]; int lowcost[105]; bool inQueue[105]; int n; int i,j,k; int maxn; while(scanf("%d%d",&end,&n),end!=0&&n!=0) { queue<int>Q; int maxroad=0; for(i=1;i<=100;i++)//初始化 { lowcost[i]=INF; inQueue[i]=false; for(j=1;j<=100;j++) { road[i][j]=INF; } } for(i=1;i<=n;i++)//初始化图矩阵 { int a,b,c; scanf("%d%d%d",&a,&b,&c); road[b][a]=road[a][b]=c; maxroad=max(max(maxroad,a),b); } lowcost[1]=0; Q.push(start); inQueue[start]=true; while(!Q.empty()) { int temp=Q.front(); for(i=2;i<=maxroad;i++) { if(i!=temp) { if(lowcost[temp]+road[temp][i]<lowcost[i]) { lowcost[i]=lowcost[temp]+road[temp][i]; if(inQueue[i]==false) { Q.push(i); inQueue[i]=true; } } } } Q.pop(); inQueue[temp]=false; } printf("%d\n",lowcost[end]); } return 0;}
转载于:https://www.cnblogs.com/Skyxj/p/3180490.html
