就是求所有可能路徑中每段中最大長(zhǎng)度的最小值
用了一個(gè)類似FLOYED的方法
代碼如下
? ???
#include <iostream>
#include <cmath>
using namespace std;
double a[202][202];
struct node
{
???? double x, y;
};
node point[202];
int main()
{
???? int n, t = 1,i,j,k;
???? while(scanf("%d", &n) && n)
???? {
???????? for( i = 1; i <= n; i++)
???????????? cin >> point[i].x >> point[i].y;
???????? for( i = 1; i <= n; i++)
???????? {
???????????? a[i][i] = 0;
???????????? for( j = i+1; j <= n; j++)
???????????? {
???????????????? a[j][i] = a[i][j] = sqrt((point[i].x - point[j].x)*(point[i].x - point[j].x)
???????????????????? + (point[i].y - point[j].y)*(point[i].y - point[j].y));
???????????? }
???????? }
???????? for(int k = 1; k <= n; k++)
???????????? for(int i = 1; i <= n; i++)
???????????????? for(int j = 1; j <= n; j++)
???????????????? {
???????????????????? double m = max(a[i][k], a[k][j]);
???????????????????? if(m < a[i][j]) a[i][j] = a[j][i] = m;
???????????????? }
???????? printf("Scenario #%d\n", t++);
???????? printf("Frog Distance = %.3f\n\n",a[1][2]);
???? }
}