题意:给出一个无向图,求一条0~1的路径使得路径上的最大边权最小.
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <cmath> 7 using namespace std; 8 #define inf 9999999 9 #define N 205 10 11 double g[N][N]; 12 int n; 13 struct node 14 { 15 int x,y; 16 }P[N]; 17 double dis(node a,node b) 18 { 19 return sqrt(double((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))); 20 } 21 22 void Floyd() 23 { 24 for(int k=0; k<n; k++) 25 { 26 for(int i=0; i<n; i++) 27 { 28 if(i==k||g[i][k]==inf) continue; 29 for(int j=0; j<n; j++) 30 { 31 if(j==k||g[k][j]==inf) continue; 32 g[i][j] = min(g[i][j],max(g[i][k],g[k][j])); 33 } 34 } 35 } 36 } 37 38 int main() 39 { 40 int cas = 1; 41 while(scanf("%d",&n)&&n) 42 { 43 for(int i=0; i<n; i++) 44 for(int j=0; j<n; j++) 45 { 46 if(i==j) g[i][j] = 0.0; 47 else g[i][j] = inf; 48 } 49 50 for(int i=0; i<n; i++) 51 scanf("%d%d",&P[i].x,&P[i].y); 52 for(int i=0; i<n; i++) 53 for(int j=0; j<n; j++) 54 { 55 if(i==j) continue; 56 g[i][j] = dis(P[i],P[j]); 57 } 58 Floyd(); 59 printf("Scenario #%d ",cas++); 60 printf("Frog Distance = %.3f ",g[0][1]); 61 } 62 return 0; 63 }