c125. Frogger
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個整數xi，yi（0 <= xi，yi <= 1000）代表第i顆石頭的座標。其中第一顆為Freddy所在的石頭，第二顆為Fiona所在的石頭，其他的n-2顆石頭上則是空的。
每組測試資料後有一空白列，當n=0時代表輸入結束。請參考Sample Input。
輸出說明 ：
對每一組測試資料，輸出一列這是第幾組測試資料，以及一列蛙跳距離。
每組測試資料後亦輸出一空白列。請參考Sample Output。
範例輸入 ：
2 0 0 3 4 3 17 4 19 4 18 5 0
範例輸出 ：
Scenario #1 Frog Distance = 5.000 Scenario #2 Frog Distance = 1.414
提示 ：
* 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;
}