Problem Description 在每年的校賽里，所有進入決賽的同學都會獲得一件很漂亮的t-shirt。但是每當我們的工作人員把上百件的衣服從商店運回到賽場的時候，卻是非常累的！所以現在他們想要尋找最短的從商店到賽場的路線，你可以幫助他們嗎？ Input 輸入包括多組數據。每組數據第一行是兩個 ...
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
#include<bits/stdc++.h> using namespace std; #define inf 99999999 int main() { int n,m,u,v,w,i,j,e[105][105],dis[105],book[105],minn; while(cin>>n>>m,n||m) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j) e[i][j]=0; else e[i][j]=inf; for(i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); e[u][v]=e[v][u]=w; } for(i=1;i<=n;i++) dis[i]=e[1][i]; for(i=1;i<=n;i++) book[i]=0; book[1]=1; for(i=1;i<=n-1;i++) { minn=inf; for(j=1;j<=n;j++)//找離原點最近的點 { if(book[j]==0&&dis[j]<minn) { minn=dis[j]; u=j; } } book[u]=1; for(v=1;v<=n;v++) { if(e[u][v]<inf&&dis[v]>dis[u]+e[u][v]) dis[v]=dis[u]+e[u][v]; } } cout<<dis[n]<<endl; } return 0; }
