Posted on 2010-08-14 18:28
MiYu 閱讀(822)
評論(0) 編輯 收藏 引用 所屬分類:
ACM ( 最短路 )
MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
題目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2544
題目描述:
最短路
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3844 Accepted Submission(s): 1628
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
題目分析:
最短路的入門題目, 我也是剛剛接觸, 開始一直沒看明白到底怎么回事, 睡了一覺醒來, 把數據結構書翻出來復習了一次 Dijkstra 終于明白了.
Dijkstra算法的基本思路是：
假設每個點都有一對標號 (dj, pj)，其中dj是從起源點s到點j的最短路徑的長度 (從頂點到其本身的最短路徑是零路(沒有弧的路)，其長度等于零)；
pj則是從s到j的最短路徑中j點的前一點。求解從起源點s到點j的最短路徑算法的基本過程如下：
1) 初始化。起源點設置為：① ds=0, ps為空;② 所有其他點: di=∞, pi=?;③ 標記起源點s，記k=s,其他所有點設為未標記的。
2) 檢驗從所有已標記的點k到其直接連接的未標記的點j的距離，并設置：
dj=min［dj, dk+lkj］
式中，lkj是從點k到j的直接連接距離。
3) 選取下一個點。從所有未標記的結點中，選取dj 中最小的一個i：
di=min［dj, 所有未標記的點j］
點i就被選為最短路徑中的一點，并設為已標記的。
4) 找到點i的前一點。從已標記的點中找到直接連接到點i的點j*，作為前一點,設置：i=j*
5) 標記點i。如果所有點已標記，則算法完全推出，否則，記k=i，轉到2) 再繼續。
代碼如下:
#include <iostream>
using namespace std;
const int INF = 0x7FFFFFFF;
const int MAX = 105;
int graph[MAX][MAX];
int N,M;
int Dijkstra ( int beg, int end )
{
bool hash[N+1];
int path[N+1];
for ( int i = 0; i <= N; ++ i )
{
hash[i] = true;
path[i] = INF;
}
hash[beg] = false;
path[beg] = 0;
while ( beg != end )
{
for ( int i = 1; i <= N; ++ i )
{
if ( graph[beg][i] )
{
if ( path[i] > path[beg] + graph[beg][i] )
path[i] = path[beg] + graph[beg][i];
}
}
int min = INF;
for ( int i = 1; i <= N; ++ i )
{
if ( min > path[i] && hash[i] )
{
min = path[i];
beg = i;
}
}
hash[beg] = false;
}
return path[end];
}
int main ()
{
while ( scanf ( "%d%d",&N,&M ) , N + M )
{
memset ( graph , 0 , sizeof ( graph ) );
for ( int i = 1; i <= M; ++ i )
{
int r,c,cost;
scanf ( "%d%d%d",&r,&c,&cost );
if ( graph[r][c] == 0 )
graph[r][c] = graph[c][r] = cost ;
else
{
if ( cost < graph[r][c] )
graph[r][c] = graph[c][r] = cost ;
}
}
cout << Dijkstra ( 1,N ) << endl;;
}
return 0;
}