題意:在一無向圖中，有 c 座城市、 s 條街道、 q 個詢問， s 條街道的起點終點與噪音值，q 個詢問中，每個詢問會包含兩個城市 A、B，問從 A 走到 B 的路徑中，所需 "忍受" 的最小噪音值。
解法: 想法跟最短路徑有點像，且會詢問任兩點的最小的路徑間最大噪音，所以想到 Floyd Warshall。
關鍵 pseudocode
FOR( k, 1, c ) FOR( i, 1, c ) FOR( j, 1, c )
edge[i][j] = min( edge[i][j], min( edge[i][k], edge[k][j] ) );
TAG: Floyd Warshall
注意:
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽