題目網址: http://goo.gl/gIxJeD
題意: 給定B個基地台，C個城市，R條路，每條路包含兩城市，代表兩程式間有路連接，以及Q個問題，使用者的設備會選擇離所在點距離最近的基地台連接，若從一基地台轉移至另一基地台的話需要一次切換，每個問題問從S城市至D城市所需最少切換次數。
解法: 題目很明白的表明要求最少切換次數，也就是最短路徑，而可以詢問Q次，所以應使用Floyd Warshall來求任兩點間的最短路徑，剩下的問題就是如何建圖，對於每條邊，邊的權重即為邊的兩端點A、B從A走至B需要切換的次數，若A、B屬於同一個基地台，那切換次數就是0，若非，則若AB間的間隔已經非常小，表示他們剛好介於兩個基地台間的中垂線上，故切換次數為1，否則以2分法，找出兩端點的中點M，而分別求出A至M的切換次數加上M至B的切換次數。
TAG: Floyd Warshall
注意: 需要精度判斷
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽