切換
舊版
前往
大廳
主題

ZeroJudge - a674: 10048 - Audiophobia 解題心得

Not In My Back Yard | 2020-06-30 00:27:17 | 巴幣 2 | 人氣 154

題目連結:


題目大意:
輸入有多筆測試資料。每筆第一列輸入給定三正整數 C 、 S 、 Q (C ≦ 100 , S ≦ 1000 , Q ≦ 10000),代表有 C 個點(編號為 1 ~ C)、這 C 個點之間有 S 個街道,並有 Q 筆的詢問。

接著有 S 列的輸入,每列給定三整數 C1 、 C2 、 d (C1 ≠ C2),代表 C1 到 C2 有一個街道,而該街道上的平均噪音為 d 分貝。

再接著有 Q 列輸入,每列給定兩整數 C1 、 C2 。試問,點 C1 到點 C2 的路徑上須忍受的最大噪音值的最小可能值為何?如果兩點沒有路徑互通,則輸出「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


解題思維:
因為詢問的是 Q 對的任意兩點間的路徑上的最大分貝值最小可以為何,因此 Floyd-Warshall 演算法可以解決此題,類似於這題

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作