想想看你何其幸運，能夠呼吸並且還能快樂的寫程式。但是我們憂慮我們的子孫可能就沒有這麼幸運了。你知道的，地球正面臨許多的污染，環境的或是社會的污染。我們的漠視也加重污染的擴展。
現在我們要談的是「噪音」的污染。一般我們以「分貝」當作聲音大小的單位。超過 130 分貝的噪音會讓人很不舒服，談話的聲音大概是 60 到 65 分貝，繁忙吵雜的交通大概是 70 到 80 分貝。
以下的城市地圖中邊代表街道，點代表路口。在邊上的整數代表這條街平均的噪音大小。
要從路口 A 到路口 G，你可以走這樣的路徑：A-C-F-G，而你必須忍受的最大噪音就是 140 分貝。如果你走的路徑是 A-B-E-G，或 A-B-D-G，或 A-C-F-D-G，那你必須忍受的最大噪音分別是 90, 120 和 80 分貝。當然還有其他路徑，但是明顯的 A-C-F-D-G 是最舒服的路徑了，因為你不必忍受超過80分貝的噪音。
在這個問題中，給你城市的地圖，請你找出你至少要能忍受多大的噪音才能從某個路口到另一個路口。
輸入包含多組測試資料。每組測試資料的第一列含有3個整數 𝐶 (≤ 100）、𝑆 (≤1000) 和 𝑄 (≤ 10000）。𝐶 代表點的數目 (點的號碼從 1 到 𝐶），𝑆 則代表街道的數目，𝑄 代表這組測試資料中有多少個小問題。
接下來的 𝑆 列，每列有三個整數 𝑐1, 𝑐2 和 𝑑。代表連接路口 𝑐1 及路口 𝑐2 (𝑐1 ≠ 𝑐2) 的街道其平均噪音是 𝑑 分貝。
再接下來的 𝑄 列每列有 2 個整數 𝑐1, 𝑐2 (𝑐1 ≠ 𝑐2），就是要請你算出從路口 𝑐1 到路口 𝑐2 你至少必須能忍受多大的噪音。
當 𝐶, 𝑆, 𝑄 由三個 0 構成時代表輸入結束。
對每組測試資料先參考範例輸出列出這是第幾組測試資料，然後對每個小問題輸出從路口 𝑐1 到路口 𝑐2 你至少必須能忍受的多大的噪音。如果該路徑不存在，請輸出 no path。
各組測試資料間請輸出一空白列。
7 9 3 1 2 50 1 3 60 2 4 120 2 5 90 3 6 50 4 6 80 4 7 70 5 7 40 6 7 140 1 7 2 6 6 2 7 6 3 1 2 50 1 3 60 2 4 120 3 6 50 4 6 80 5 7 40 7 5 1 7 2 4 0 0 0
Case #1 80 60 60 Case #2 40 no path 80
公開 測資點#0 (100%): 1.0s , <1M
Lucky貓 ★★★
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||