D - 最短路徑·一
HihoCoder - 1081
描述
萬(wàn)圣節(jié)的早上丑蛤，小Hi和小Ho在經(jīng)歷了一個(gè)小時(shí)的爭(zhēng)論后录平，終于決定了如何度過(guò)這樣有意義的一天——他們決定去闖鬼屋随常！
在鬼屋門口排上了若干小時(shí)的隊(duì)伍之后，剛剛進(jìn)入鬼屋的小Hi和小Ho都頗饑餓萄涯，于是他們決定利用進(jìn)門前領(lǐng)到的地圖，找到一條通往終點(diǎn)的最短路徑唆鸡。
鬼屋中一共有N個(gè)地點(diǎn)涝影，分別編號(hào)為1..N，這N個(gè)地點(diǎn)之間互相有一些道路連通争占，兩個(gè)地點(diǎn)之間可能有多條道路連通燃逻，但是并不存在一條兩端都是同一個(gè)地點(diǎn)的道路。那么小Hi和小Ho至少要走多少路程才能夠走出鬼屋去吃東西呢臂痕？
提示：順序伯襟！順序才是關(guān)鍵。×Close
提示：順序握童！順序才是關(guān)鍵姆怪。
小Ho想了想說(shuō)道：“唔……我覺得動(dòng)態(tài)規(guī)劃可以做，但是我找不到計(jì)算的順序澡绩，如果我用f[i]表示從S到達(dá)編號(hào)為i的節(jié)點(diǎn)的最短距離的話稽揭，我并不能夠知道f[1]..f[N]的計(jì)算順序》士ǎ”
“所以這個(gè)問題不需要那么復(fù)雜的算法啦溪掀，我就稍微講講你就知道了！”小Hi道：“路的長(zhǎng)度不可能為負(fù)數(shù)對(duì)不對(duì)步鉴？”
“那是自然揪胃，畢竟人類還沒有發(fā)明時(shí)光機(jī)器……”小Ho點(diǎn)點(diǎn)頭璃哟。
于是小Hi問道：“那么如果就看與S相鄰的所有節(jié)點(diǎn)中與S最近的那一個(gè)S'，并且從S到S'的距離為L(zhǎng)喊递，那么有可能存在另外的道路使得從S到S'的距離小于L么随闪？”
“不能，因?yàn)镾'是與S相鄰的所有節(jié)點(diǎn)中與S最近的節(jié)點(diǎn)册舞，那么從S到其他相鄰點(diǎn)的距離一定是不小于L的蕴掏，也就是說(shuō)無(wú)論接下來(lái)怎么走，回到L點(diǎn)時(shí)總距離一定大于L调鲸∈⒔埽”小Ho思考了一會(huì)，道藐石。
“也就是說(shuō)你已經(jīng)知道了從S到S'的最短路徑了是么即供？”小Hi繼續(xù)問道。
“是的于微，這條最短路徑的長(zhǎng)度是L逗嫡。”小Ho答道株依。
小Hi繼續(xù)道：“那么現(xiàn)在驱证，我們不妨將S同S'看做一個(gè)新的節(jié)點(diǎn)？稱作S1恋腕，然后我就計(jì)算與S相鄰或者與S'相鄰的所有節(jié)點(diǎn)中抹锄，與S最近的哪一個(gè)節(jié)點(diǎn)S''。注意荠藤，在這個(gè)過(guò)程中伙单，與S相鄰的節(jié)點(diǎn)與S的距離在上一步就已經(jīng)求出來(lái)了，那么我要求的只有與S'相鄰的那些節(jié)點(diǎn)與S的距離——這個(gè)距離等于S與S'的距離加上S'與這些結(jié)點(diǎn)的距離哈肖，對(duì)于其中重復(fù)的節(jié)點(diǎn)——同時(shí)與S和S'相鄰的節(jié)點(diǎn)吻育，取兩條路徑中的較小值∮倬”
小Ho點(diǎn)了點(diǎn)頭：“那么同之前一樣布疼，與S1（即S與S'節(jié)點(diǎn)）相鄰的節(jié)點(diǎn)中與S'距離最近的節(jié)點(diǎn)如果是S''的話，并且這個(gè)距離是L2庄吼，那么我們可以知道S到S''的最短路徑的長(zhǎng)度便是L2缎除，因?yàn)椴豢赡艽嬖诹硗獾牡缆繁冗@個(gè)更短了∽苎埃”
于是小Hi總結(jié)道：“接下來(lái)的問題不就很簡(jiǎn)單了么器罐，只需要以此類推，每次將與當(dāng)前集合相鄰（即與當(dāng)前集合中任意一個(gè)元素）的所有節(jié)點(diǎn)中離S最近的節(jié)點(diǎn)（這些距離可以通過(guò)上一次的計(jì)算結(jié)果推導(dǎo)而出）選出來(lái)添加到當(dāng)前集合中渐行，我就能夠保證在每一個(gè)節(jié)點(diǎn)被添加到集合中時(shí)所計(jì)算的離S的距離是它與S之間的最短路徑轰坊！”
“原來(lái)是這樣铸董！但是我的肚子更餓了呢！”言罷肴沫，小Ho的肚子咕咕叫了起來(lái)粟害。
Close
輸入
每個(gè)測(cè)試點(diǎn)（輸入文件）有且僅有一組測(cè)試數(shù)據(jù)。
在一組測(cè)試數(shù)據(jù)中：
第1行為4個(gè)整數(shù)N颤芬、M悲幅、S、T站蝠，分別表示鬼屋中地點(diǎn)的個(gè)數(shù)和道路的條數(shù)汰具，入口（也是一個(gè)地點(diǎn)）的編號(hào)，出口（同樣也是一個(gè)地點(diǎn)）的編號(hào)菱魔。
接下來(lái)的M行留荔，每行描述一條道路：其中的第i行為三個(gè)整數(shù)u_i, v_i, length_i，表明在編號(hào)為u_i的地點(diǎn)和編號(hào)為v_i的地點(diǎn)之間有一條長(zhǎng)度為length_i的道路澜倦。
對(duì)于100%的數(shù)據(jù)聚蝶，滿足N<=103，M<=104, 1 <= length_i <= 10^3, 1 <= S, T <= N, 且S不等于T藻治。
對(duì)于100%的數(shù)據(jù)碘勉，滿足小Hi和小Ho總是有辦法從入口通過(guò)地圖上標(biāo)注出來(lái)的道路到達(dá)出口。
輸出
對(duì)于每組測(cè)試數(shù)據(jù)桩卵，輸出一個(gè)整數(shù)Ans恰聘，表示那么小Hi和小Ho為了走出鬼屋至少要走的路程。
Sample Input
5 23 5 4
1 2 708
2 3 112
3 4 721
4 5 339
5 4 960
1 5 849
2 5 98
1 4 99
2 4 25
2 1 200
3 1 146
3 2 106
1 4 860
4 1 795
5 4 479
5 4 280
3 4 341
1 4 622
4 2 362
2 3 415
4 1 904
2 1 716
2 5 575
Sample Output
123
解法：Dijkstra算法吸占，計(jì)算從一個(gè)確定結(jié)點(diǎn)到所有其他結(jié)點(diǎn)的最小距離，設(shè)源點(diǎn)為k凿宾，數(shù)組a用來(lái)存放所有節(jié)點(diǎn)到k的距離矾屯，如果k和i之間有邊則a[i]為邊長(zhǎng)，否則設(shè)置成無(wú)窮大初厚。再找與k相鄰的結(jié)點(diǎn)件蚕，找到這些結(jié)點(diǎn)相鄰的結(jié)點(diǎn)j，如果a[j]>a[i]+b[i][j]則a[j]的值更新产禾，直到找到目的結(jié)點(diǎn)排作。
代碼：
#include<iostream>
#include<cstdio>
#include<limits.h>
using namespace std;
int a[1005];
int b[1005][1005];
bool vis[1005];
int main()
{
int n,m,s,t;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=0;i<m;i++){
int x,y,z;
cin>>x>>y>>z;
if(b[x][y]==0){
b[x][y]=z;
b[y][x]=z;
}
else if(b[x][y]>z){
b[x][y]=z;
b[y][x]=z;
}
}
for(int i=1;i<=n;i++){
if(i==s)
a[i]=0;
else if(b[s][i]!=0)
a[i]=b[s][i];
else
a[i]=INT_MAX;
}
vis[s]=1;
while(1){
int dis=INT_MAX,now;
for(int i=1;i<=n;i++){
if(vis[i]==0&&a[i]<dis){
dis=a[i];
now=i;
}
}
vis[now]=1;
if(now==t){
cout<<dis<<endl;
break;
}
for(int i=1;i<=n;i++){
if(b[now][i]!=0&&b[now][i]+dis<a[i])
a[i]=b[now][i]+dis;
}
}
}
