最短路
弗洛伊德/迪杰斯特拉
/*题意：一个二逼小青蛙跳啊跳，跳啊跳，他要去拜访另一个青蛙 求他到那个青蛙有n条通路，每条通路中都有一个最大边，求这些最大边中的最小边， 最短路的思想，每个节点dis数组里面存的是从源点所有到这个点的通路里面最大的那条边； 迪杰斯特拉， dis[j]=min(dis[j],max(dis[u],s[u][j])); */ #include <iostream> #include <math.h> #include <stdio.h> #include <string.h> #include <queue> #include <algorithm> #include <math.h> #define INF 0x3f3f3f3f using namespace std; struct node { int a; int b; } c[505]; int s[505][505],dis[505]; int vis[505],n,f; void tree() { memset(vis,0,sizeof(vis)); for(int i=1; i<n; i++) { if(s[0][i]) { dis[i]=s[0][i]; } else { dis[i]=INF; } } vis[0]=1; int l; int min1; for(int k=0; k<n; k++) { min1=INF; for(int i=1; i<n; i++) { if(dis[i]<min1&&vis[i]==0) { l=i; min1=dis[i]; } } vis[l]=1; for(int j=0; j<n; j++) { if(s[l][j]>0&&vis[j]==0) { int max1=dis[l]; if(s[l][j]>max1) { max1=s[l][j]; } if(dis[j]>max1) { dis[j]=max1; } } } } printf("Scenario #%d Frog Distance = %.3f ",f++,sqrt(dis[1])); } int main() { int x1,x2,x3,x4,ck; f=1; while(~scanf("%d",&n)&&n) { ck=0; scanf("%d %d %d %d",&x1,&x2,&x3,&x4); c[ck].a=x1; c[ck++].b=x2; c[ck].a=x3; c[ck++].b=x4; int k=n-2; while(k--) { scanf("%d%d",&x1,&x2); c[ck].a=x1; c[ck++].b=x2; } memset(s,0,sizeof(s)); for(int i=0; i<ck; i++) { for(int j=0; j<ck; j++) { x1=c[i].a; x2=c[i].b; x3=c[j].a; x4=c[j].b; s[i][j]=s[j][i]=(x1-x3)*(x1-x3)+(x2-x4)*(x2-x4); } } tree(); } return 0; }