http://acm.pku.edu.cn/JudgeOnline/problem?id=2253
#include<iostream>
#include<cmath>
using namespace std;
#define MAXN 1002
#define inf 1000000000
typedef double elem_t;
elem_t mat[MAXN][MAXN];
elem_t dist[MAXN];
int num[MAXN][2];
double distance(int a1,int a2,int b1,int b2)
{
return sqrt((double)((a1-b1)*(a1-b1)+(a2-b2)*(a2-b2)));
}
void dijkstra(int n,int s)
{
int v[MAXN],i,j;
int k;
for (i=0;i<n;i++)
dist[i]=mat[s][i],v[i]=0;//初始化
for (dist[s]=0,j=0;j<n;j++){
for (k=-1,i=0;i<n;i++)//估計計距離最小的頂點k
if (!v[i]&&(k==-1||dist[i] < dist[k]))
k=i;
for (v[k]=1,i=0;i<n;i++)
if (!v[i] && mat[k][i]>0.0)//&& max(dist[k],mat[k][i]) > dist[i])
{
dist[i] = min( max(dist[k],mat[k][i]),dist[i]);
//dist[i]=min(dist[k],mat[k][i]);
}
}
}
int main()
{
int n,m,k,x1,y1;
for(int i = 1;;i ++){
scanf("%d",&n);
if( n == 0)break;
memset(mat,0,sizeof(mat));
for( int j=0;j<n;j++)
scanf("%d %d",&num[j][0],&num[j][1]);
for( int k=0;k<n;k++)
for( int j=0;j<n;j++){
mat[k][j]=distance(num[k][0],num[k][1],num[j][0],num[j][1]);
}
dijkstra(n,0);
printf("Scenario #%d\n",i);
printf("Frog Distance = %0.3lf\n\n",dist[1]);//dist[n-1]<<endl<<endl;
}
return 0;
}
/**//*
1
3 3
1 2 3
1 3 4
2 3 5
*/
posted on 2008-11-06 21:55
爬 閱讀(1852)
評論(6) 編輯 收藏 引用 所屬分類:
pku