背景

　　圣誕節又要到了！小薩希望和自己心儀的MM一起出去度過一個浪漫的的圣誕節。他進行了詳盡的準備，找到了N個很適合他們去約會的好地方，但無奈小薩和他的MM都是初三學校，晚上必須回學校上晚修，沒有足夠的時間讓他們走遍每一個地方。迫于無奈，小薩選擇了一個最合適的地方S。小薩打算和他的MM一起步行到那個地方，那樣他們就有很多時間來聊天玩樂，但是無奈時間有限，小薩決定坐公共汽車過去。然而，小薩發覺，自己的錢只夠買一張公共汽車車票了！小薩該怎么辦呢？他找到了你……
【題目描述】
　　小薩將給出一張地圖，它可以看做一個有N（N<=100）個結點的圖。這張地圖有N個公共汽車站，小薩只可以在這N個汽車站上公共汽車。有些車站之間存在一條雙向通路，無論是公共汽車還是小薩，都只能走這些通路。若兩個車站之間的距離為d，步行所需要的時間為2*d秒，坐公共汽車所需要的時間為d秒。小薩他們只有T秒的時間，他希望你求出他和他的MM出去約會后能否及時趕回來，若不能，則輸出“You are day dreaming!”，否則輸出他們所需要花費的最少時間。
注意：一張公共汽車車票可以使用兩次（只可以搭乘同一輛公共汽車），即可以認為小薩去約會地點的時間和回來的時間相等。

Input

第一行有三個整數N、T、S
接下來是一個N*N的鄰接矩陣。兩兩車站之間的距離不超過10^9。A[I,j]為0表示I和J車站不連通。

Output

若小薩他們不能在限定時間內趕回學校，那么輸出“You are day dreaming!”（不包括引號）
否則，輸出一個整數，為他們所需要花費的最少時間。

Sample Input

4 5 4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
Sample Output

2
Hint

【數據范圍】
20%的數據：N<=10
100%的數據：N<=70 T<=10^9

---

因為公共汽車是來回使用的（坐車的時間一定比走路的耗時少，【其實，誰知道小薩不是閃電俠呢！】）

分析：

①將讀入的距離乘2
②枚舉第i個點坐公共汽車坐到第j個點
③用dij求第1到i的走路的耗時+第i到j乘車的耗時+第j到s走路的耗時
④判斷是否為最小的耗時，是則更新
⑤輸出最小耗時

---

代碼如下：

vara:array [0..101,0..101] of longint;b:array [0..101] of longint;f:array [0..101] of boolean;n,min,t,s:longint; procedure init; vari,j:longint; beginreadln(n,t,s);for i:=1 to n dofor j:=1 to n dobeginread(a[i,j]);if a[i,j]=0 then a[i,j]:=maxlongintelse a[i,j]:=a[i,j]*2;end; end;procedure main; vari,j,t:longint; beginfor i:=1 to n dob[i]:=a[1,i];fillchar(f,sizeof(f),true);f[1]:=false;for i:=1 to n-1 dobeginmin:=maxlongint;for j:=1 to n doif f[j] and (b[j]<min) thenbeginmin:=b[j];t:=j;end;f[t]:=false;for j:=1 to n doif f[j] and (a[t,j]<>maxlongint) and (b[t]+a[t,j]<b[j]) thenb[j]:=b[t]+a[t,j];end; end;procedure immain; vari,j,min:longint; beginmin:=maxlongint;for i:=1 to n dofor j:=1 to n doif a[i,j]<>maxlongint thenbegina[i,j]:=a[i,j] div 2;main;if b[s]<min then min:=b[s];a[i,j]:=a[i,j]*2;end;if min*2>t then write('You are day dreaming!')else write(min*2); end;begininit;main;immain; end.

轉載于:https://www.cnblogs.com/Comfortable/p/8412332.html

總結

以上是生活随笔為你收集整理的SSL 1624——小萨的烦恼【最短路】【枚举】的全部內容，希望文章能夠幫你解決所遇到的問題。

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