Bessie Come Home回家

(comehome.pas)

【問題描述】

現(xiàn)在是晚餐時間,而母牛們在外面分散的牧場中。農(nóng)民約翰按響了電鈴,所以她們開始向谷倉走去。你的工作是要指出哪只母牛會最先到達谷倉(在給出的測試數(shù)據(jù)中,總會有且只有一只最快的母牛)。在擠奶的時候(晚餐前),每只母牛都在她自己的牧場上,一些牧場上可能沒有母牛。每個牧場由一條條道路和一個或多個牧場連接(可能包括自己)。有時，兩個牧場(可能是字母相同的)之間會有超過一條道路相連。至少有一個牧場和谷倉之間有道路連接。因此,所有的母牛最后都能到達谷倉,并且母?？偸亲咦疃痰穆窂健．斎?母牛能向著任意一方向前進,并且她們以相同的速度前進。牧場被標記為'a'..'z'和'A'..'Y',在用大寫字母表示的牧場中有一只母牛,小寫字母中則沒有。谷倉的標記是'Z',注意沒有母牛在谷倉中。

注意'm'和'M'不是同一個牧場 否則錯誤 上面的意思是說：輸入數(shù)據(jù)中可能會同時存在M,m（郁悶ing)，比如?

M a a m m z?

【輸入格式】(comehome.in)?

第 1?行:?整數(shù) P(1<= P<=10000),表示連接牧場(谷倉)的道路的數(shù)目。

第 2 ..P+1行:?用空格分開的兩個字母和一個整數(shù):?

被道路連接牧場的標記和道路的長度(1<=長度<=1000)。?

【輸出格式】(comehome.out)?

單獨的一行包含二個項目:?最先到達谷倉的母牛所在的牧場的標記,和這只母牛走過的路徑的長度。

【樣例輸入】(comehome.in)?

5

A d 6

B d 3

C e 9

d Z 8

e Z 3

【樣例輸出】

B 11

【思路分析】

?此題可以簡化為一個求最短路的算法：

???? 把‘Z’ 點當做一個根節(jié)點然后用迪斯卡爾算法求到每一個‘A'..’Y' 中最小值即可??！

【參考程序】文章來源地址http://www.zghlxwxcb.cn/news/detail-668016.html

var dist:array['A'..'z','A'..'z'] of longint;
??? n,m,max,d,min:longint;
??? v:array['A'..'z'] of boolean;
??? vv:array['A'..'Z'] of boolean;
??? i,j,k:char;
??? ch1,ch2,ch:char;
begin
? assign(input,'comehome.in');reset(input);
? assign(output,'comehome.out');rewrite(output);
? readln(n);
?? fillchar(vv,sizeof(vv),false);
?? fillchar(v,sizeof(v),false);
?? for d:=1 to n do
??? begin
???? readln(ch1,ch,ch2,min);
???? if (dist[ch1,ch2]<>0)and(dist[ch1,ch2]<min) then? dist[ch1,ch2]:=dist[ch1,ch2];
???? if (dist[ch1,ch2]<>0)and(dist[ch1,ch2]>min) then? dist[ch1,ch2]:=min;
???? if dist[ch1,ch2]=0 then dist[ch1,ch2]:=min;
???? dist[ch2,ch1]:=dist[ch1,ch2];
???? if (ch1>='A')and(ch1<='Z') then
????? vv[ch1]:=true;
??? end;
?? v['Z']:=true;
?? for i:='A' to 'z' do
??? begin
????? if (ord(i)>90)and(ord(i)<97) then continue;
?????? max:=maxlongint;
????? for j:='A' to 'z' do
??????? if (dist['Z',j]<>0)and(dist['Z',j]<max)and(not v[j]) then
???????? begin
????????? max:=dist['Z',j];
????????? k:=j;
???????? end;
????? v[k]:=true;
???? for j:='A' to 'z' do
????? if dist[k,j]>0 then
?????? if (dist['Z',k]+dist[k,j]<dist['Z',j])or(dist['Z',j]=0) then
??????? dist['Z',j]:=dist['Z',k]+dist[k,j];
??? end;
???? min:=maxlongint;
?? for i:='A' to 'Y' do
?? if vv[i] then
??? begin
???? if (dist['Z',i]<min)and(dist['Z',i]<>0) then
????? begin
?????? k:=i;
?????? min:=dist['Z',i];
????? end;
??? end;
? writeln(k,' ',min);
?close(input); close(output);
end.

到了這里，關(guān)于Bessie Come Home回家 NOIP題解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！