最短路

Time Limit: 5000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 84780????Accepted Submission(s): 36719

?

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; const int inf = 0x3f3f3f3f; const int maxn = 1010; int a[maxn][maxn],dis[maxn]; bool vis[maxn]; int n,m; void Dijkstra(int x) {dis[x]=0;for(int i=1;i<=n;i++){int minn=inf,pos;for(int j=1;j<=n;j++){if(!vis[j]&&dis[j]<minn){pos=j;minn=dis[j];}}vis[pos]=true;for(int j=1;j<=n;j++){if(dis[pos]+a[pos][j]<dis[j]&&!vis[j])dis[j]=dis[pos]+a[pos][j];}}return ; } int main() {while(scanf("%d%d",&n,&m),n){memset(a,inf,sizeof(a));memset(vis,0,sizeof(vis));memset(dis,inf,sizeof(dis));for(int i=0; i<m; i++){int x,y,w;scanf("%d%d%d",&x,&y,&w);if(w<a[x][y])a[x][y]=a[y][x]=w;}Dijkstra(1);printf("%d\n",dis[n]);}return 0; }

?

總結

以上是生活随笔為你收集整理的hdu-2544（简单djikstra）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。