c125. Frogger＠Morris' Blog｜PChome Online 個人新聞台

2011-06-15 07:39:05| 人氣1,310| 回應0 | 上一篇 | 下一篇

c125. Frogger

推薦 0 收藏 0 轉貼0 訂閱站台

http://zerojudge.tw/ShowProblem?problemid=c125

內容：

有一隻叫做Freddy的青蛙坐在湖中央的一塊石頭上，突然間他發現另一隻青蛙（她的名字是Fiona）坐在另一顆石頭上。他想要過去找她，但是因為湖水很髒，到處充滿著遊客的防曬油，所以他決定用跳的，而不要用游的。

不妙的是Fiona的石頭離他的距離超出他所能跳的範圍。因此Freddy考慮利用其他的一些石頭當作中繼站，因此他就可以跳比較小的距離（或許要跳許多次）去找Fiona。

要這樣子連續的跳，很明顯的Freddy一次能跳的距離必須至少和這一串石頭間的距離最大的距離一樣。因此，介於石頭間的蛙跳距離（frog distance，人類也稱之為minmax distance）定義為要從Freddy所在的石頭要跳到Fiona所在的石頭的路徑中，最小必須要跳的距離。

給你Freddy所在的石頭、Fiona所在的石頭，以及湖中所有其他石頭的座標，你的任務是算出介於Freddy和Fiona所在石頭間的蛙跳距離。

輸入說明：

輸入含有多組測試資料。每組測試資料的第一列有1個整數n，代表石頭的數目（2 <= n <= 200）。接下來的n列每列有2個整數x_i，y_i（0 <= x_i，y_i<= 1000）代表第i顆石頭的座標。其中第一顆為Freddy所在的石頭，第二顆為Fiona所在的石頭，其他的n-2顆石頭上則是空的。

每組測試資料後有一空白列，當n=0時代表輸入結束。請參考Sample Input。

輸出說明：

對每一組測試資料，輸出一列這是第幾組測試資料，以及一列蛙跳距離。

每組測試資料後亦輸出一空白列。請參考Sample Output。

範例輸入：

範例輸出：

Scenario #1
Frog Distance = 5.000

Scenario #2
Frog Distance = 1.414

提示：

背景知識： Shortest Path

* Luck 貓翻譯

出處：

/**********************************************************************************/
/* Problem: c125 "Frogger" from ACM 534                                          */
/* Language: C                                                                   */
/* Result: AC (6ms, 774KB) on ZeroJudge                                          */
/* Author: morris1028 at 2011-06-14 18:58:06                                     */
/**********************************************************************************/

#include<stdio.h>
#include<math.h>
struct coordinate {
   int x, y;
}D[200];
struct link {
   double t;
   int index;
}Map[200][200];
double SPFA(int n) {
   double V[200], t;
   int a, b, Queue[40000], Qt = 0, Used[200] = {}, tn;
   for(a = 0; a < n; a++)   V[a] = 2000;
   Queue[0] = 0, V[0] = 0;
   for(a = 0; a <= Qt; a++) {
       tn = Queue[a], Used[tn] = 0;
       for(b = 0; b < n; b++) {
           t = V[tn] > Map[tn][b].t ? V[tn] : Map[tn][b].t;
           if(V[Map[tn][b].index] > t) {
               V[Map[tn][b].index] = t;
               if(Used[Map[tn][b].index] == 0) {
                   Used[Map[tn][b].index] = 1, Queue[++Qt] = Map[tn][b].index;
               }
           }
       }
   }
   return V[1];
}
main() {
   int n, a, b, c, C = 0;
   while(scanf("%d", &n) == 1 && n) {
       for(a = 0; a < n; a++)
           scanf("%d %d", &D[a].x, &D[a].y);
       for(a = 0; a < n; a++) {
           for(b = 0; b < n; b++) {
               Map[a][b].t = sqrt((D[a].x-D[b].x)*(D[a].x-D[b].x) + (D[a].y-D[b].y)*(D[a].y-D[b].y));
               Map[a][b].index = b;
           }
       }
       printf("Scenario #%d\n", ++C);
       printf("Frog Distance = %.3lf\n\n", SPFA(n));
   }
   return 0;
}

我要檢舉

#c125#Frogger

台長： Morris

您可能對以下文章有興趣

[UVA][bitmask] 12515 - Movie Police

[UVA][Math] 10509 - R U Kidding Mr. Feynman?

[UVA][數學] 11648 - Divide The Land

[UVA][ConvexHull&重心] 10002 - Center of Masses

人氣(1,310) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:d089. 145 - Gondwanaland Telecom
此分類上一篇:c112. Optimal Array Multiplication Sequence

回應(0)