網頁

2014年4月3日 星期四

UVa 10278 Fire Station

題意:
    有F個消防站分布在I個路口,假設每個路口i到離該路口最近的消防站距離為di,而D為這些di的最大值。今天要再增加'一個'消防站在某個路口,求要設在哪個路口使得D為最小。
想法:
  1. 先用Floyd演算法求出All pair shortest path
  2. 然後求各個路口i到離該路口最近的消防站的距離,用shortest_lenght[i]來存,並找出D值。
  3. 從1開始枚舉到I,找出能使得D值最小的路口的編號。

沒有留言:

張貼留言