Frogger

大意：

給出兩個青蛙的坐標和其他n-2個石頭的坐標，任一兩個坐標點間都是雙向連通的。現在要求求出所有通路的最大距離，并把這些最大距離作比較，把最小的一個最大距離作為青蛙的最小跳遠距離。

思路：

先求出兩兩之間的最短距離，再求出每個點開始的最長路，在這些最長路中求出那個最小的。、

?

輸出用printf怎么著都不過，直接用cout了。。。

?

1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 #include <iostream> 5 #include <algorithm> 6 #include <math.h> 7 #include <iomanip> 8 #define INF 0x3f3f3f3f 9 using namespace std; 10 11 double x[210], y[210]; 12 double Map[210][210]; 13 14 void Solve() 15 { 16 int cnt = 1; 17 int n; 18 while(~scanf("%d", &n) && n) 19 { 20 for(int i = 1; i <= n; i++) 21 { 22 scanf("%lf%lf", &x[i], &y[i]); 23 } 24 for(int i = 1; i <= n-1; i++) 25 { 26 for(int j = i+1; j <= n; j++) 27 { 28 double x2 = x[i]-x[j]; 29 double y2 = y[i]-y[j]; 30 Map[i][j] = Map[j][i] = sqrt(x2*x2+y2*y2); 31 } 32 } 33 for(int k = 1; k <= n; k++) 34 { 35 for(int i = 1; i <= n-1; i++) 36 { 37 for(int j = i+1; j <= n; j++) 38 { 39 if(Map[i][k] < Map[i][j] && Map[k][j] < Map[i][j]) 40 { 41 if(Map[i][k] < Map[k][j]) 42 { 43 Map[i][j] = Map[j][i] = Map[k][j]; 44 } 45 else 46 { 47 Map[i][j] = Map[j][i] = Map[i][k]; 48 } 49 } 50 } 51 } 52 } 53 /*printf("Scenario #1%d\n", cnt++); 54 printf("Frog Distance = %.3f\n", Map[1][2]);*/ 55 cout<<"Scenario #"<<cnt++<<endl; 56 cout<<fixed<<setprecision(3)<<"Frog Distance = "<<Map[1][2]<<endl<<endl; 57 } 58 } 59 60 int main() 61 { 62 Solve(); 63 64 return 0; 65 } Frogger

?

轉載于:https://www.cnblogs.com/Silence-AC/p/3525563.html

總結

以上是生活随笔為你收集整理的POJ 2253 Frogger（最短路 Floyd）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。