解题思路：floyed模板题（稍微变换一点），不解释，上代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 using namespace std; 6 #define inf 0x3f3f3f3f 7 const int maxn = 205; 8 double w[maxn][maxn]; 9 10 struct node{ 11 double x, y; 12 }p[maxn]; 13 14 int main() 15 { 16 int n, kase = 1; 17 while(~scanf("%d", &n) && n) 18 { 19 for(int i = 1; i <= n; i++) 20 for(int j = i; j <= n; j++) 21 { 22 if(i == j) w[i][j] = 0; 23 else w[i][j] = w[j][i] = inf; 24 } 25 26 for(int i = 1; i <= n; i++) 27 scanf("%lf %lf", &p[i].x, &p[i].y); 28 29 for(int i = 1; i <= n; i++) 30 { 31 for(int j = i; j <= n; j++) 32 { 33 double x2 = p[j].x - p[i].x; 34 double y2 = p[j].y - p[i].y; 35 36 w[i][j] = w[j][i] = sqrt(x2*x2 + y2*y2); 37 } 38 } 39 40 for(int i = 1; i <= n; i++) 41 { 42 for(int j = 1; j <= n; j++) 43 { 44 for(int k = j; k <= n; k++) 45 { 46 if(w[j][i] <= w[j][k] && w[i][k] <= w[j][k]) 47 { 48 w[j][k] = w[k][j] = max(w[j][i], w[i][k]); 49 } 50 } 51 } 52 } 53 54 printf("Scenario #%d Frog Distance = %.3lf ", kase++, w[1][2]); 55 } 56 return 0; 57 }