| ||||||||||
| 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 | |||||||||
我也WA到吐血,有哪位好心人,帮我看一下,错在何处,谢谢#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;;
double map[210][210];
int N;
double f[205];
const double INF=9999999999999;
struct p
{
double x,y;
}haha[210];
double dis(p a,p b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void dijstra()
{
bool used[205]={0};
for(int i=2;i<=N;i++)
{
f[i]=INF;
}f[1]=0;
for(int i=1;i<N;i++)
{
double min=INF;int flag=0;
for(int j=1;j<=N;j++)
{
if(!used[j]&&f[j]<min)
{
min=f[flag=j];
}
}
if(flag==0)break;
used[flag]=1;
for(int j=1;j<=N;j++)
{
if(!used[j]&&f[j]>f[flag]+map[flag][j])
f[j]=f[flag]+map[flag][j];
}
}
}
int main()
{
//freopen("t.txt","r",stdin);
for(int i=1;i<=200;i++)
for(int j=1;j<=200;j++)
map[i][j]=INF;
double a,b;
scanf("%lf%lf%lf%lf",&haha[1].x,&haha[1].y,&haha[2].x,&haha[2].y);
N=2;
while(scanf("%lf%lf",&a,&b)>0)
{
N++;
haha[N].x=a;haha[N].y=b;
while(1)
{
scanf("%lf%lf",&a,&b);
if(a==-1&&b==-1)
break;
N++;
haha[N].x=a;haha[N].y=b;
map[N-1][N]=dis(haha[N-1],haha[N])/40;
map[N][N-1]=map[N-1][N];
}
}
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
{
map[i][j]=min(map[i][j],dis(haha[i],haha[j])/10)/1000*60;
}
dijstra();
printf("%.0lf\n",f[2]);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator