Input
Output
Sample Input
2
0 0
3 4
3
17 4
19 4
18 5
0
Sample Output
Scenario #1 Frog Distance = 5.000 Scenario #2 Frog Distance = 1.414
题目意思:有一只青蛙在1处,他想到2处,求出可能的路径中最长的是最短的路径;
解题思路:改变一下改变dist的条件;
#include<iostream>
#include <string.h>
#include <math.h>
#include <stdio.h>
using namespace std;
const int MAX = 2000;
const long long MAX1 = 1e12;
int visit[MAX];
double Map[MAX][MAX];
double dist[MAX];
int path[MAX];
int N;
struct S
{
double x,y;
};
S dian[MAX];
void D()
{
for(int i = 1;i <= N;i++)
{
visit[i] = 0;
dist[i] = Map[1][i];
path[i] = 1;
}
visit[1] = 1;
long long min1;
int min1_num;
for(int i = 1;i < N;i++)
{
min1 = MAX1;
for(int i = 1;i <= N;i++)
{
if(visit[i]==0&&dist[i]<min1)
{
min1 = dist[i];
min1_num = i;
}
}
visit[min1_num] = 1;
for(int i = 1 ;i <= N;i++)
dist[i]=min(dist[i],max(dist[min1_num],Map[min1_num][i]));
}
}
int main()
{
int N0 = 0;
while(cin>>N)
{
if(N==0) break;
cout<<"Scenario #"<<++N0<<endl;
memset(Map,0,sizeof(Map));
for(int i = 1;i <= N;i++)
cin>>dian[i].x>>dian[i].y;
for(int i = 1;i <N;i++)
{
for(int j = i +1; j <= N;j++)
{
Map[i][j] = Map[j][i] = sqrt( (dian[i].x-dian[j].x)*(dian[i].x-dian[j].x)+(dian[i].y-dian[j].y)*(dian[i].y-dian[j].y) );
}
}
D();
printf("Frog Distance = %.3f\n",dist[2]);
cout<<endl;
}
return 0;
}
原文：http://www.cnblogs.com/a2985812043/p/7304880.html