D - Frogger （最短路）

D - Frogger （最短路）

题意：求1到n所有路径的最大值中最小必要值。

题目传送门

思路：

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue> 
#include<cmath>
#include<algorithm>
using namespace std;
double f[205][205];
struct p{
	double x,y;
}a[205];
double  fun(int i,int j){ //求距离 
	return hypot((a[i].x-a[j].x),(a[i].y-a[j].y));
}
int main(){
	int n,k=0;
	while(~scanf("%d",&n)&&n){
	for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			if(i==j) f[i][j]=0;
			else  f[i][j]=fun(i,j);
		}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			if(f[i][k])
				for(int j=1;j<=n;j++)
				{
					if(f[i][j]>max(f[i][k],f[k][j]))
					{
						f[i][j]=max(f[i][k],f[k][j]);
					}
				}
	printf("Scenario #%d\nFrog Distance = %.3f\n",++k,f[1][2]);//G++用%.f C++ %.lf %f都可. 
	puts("");
	}
	return 0;
}