| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
不是最短路的最短路,dij也可以变种呀~附0msdij代码#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
#define inf 0x7fffffff
int x[210],y[210],n,mark[210];
double map[210][210],v[210];
double getit(int i,int j)
{
int d;
double f;
d=(y[i]-y[j])*(y[i]-y[j])+(x[i]-x[j])*(x[i]-x[j]);
f=sqrt(d);
return f;
}
double max(double a,double b)
{
if(a>=b)
return a;
else
return b;
}
double dijkstra()
{
memset(mark,0,sizeof(mark));
int i,j,k;
double t,ans=0;
for(i=0;i<n;i++)
{
v[i]=map[0][i];
}
v[i]=0;
mark[0]=1;
for(i=1;i<n;i++)
{
t=inf; //t=v[i];
for(j=0;j<n;j++)
{
if(!mark[j]&&v[j]<t)
{
t=v[j];
k=j;
}
}
mark[k]=1;
for(j=0;j<n;j++)
{
double temp=max(map[k][j],v[k]);
if(temp<v[j])
v[j]=temp;
}
}
ans=v[1];
return ans;
}
int main()
{
int i,j,k,test=0;
double weight,ans;
while(scanf("%d",&n)==1)
{
test++;
memset(map,0,sizeof(map));
if(n==0)
break;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
map[i][j]=inf;
map[i][i]=0;
}
for(i=0;i<n;i++)
{
scanf("%d%d",&x[i],&y[i]);
for(j=0;j<i;j++)
{
weight=getit(i,j);
map[i][j]=weight;
map[j][i]=weight;
}
}
ans=dijkstra();
printf("Scenario #%d\n",test);
printf("Frog Distance = %.3f\n\n",ans);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator