| ||||||||||
| 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>
#include<iomanip>
using namespace std;
#define INF 12345678.8
double a[205][205];
struct point
{
int x;
int y;
}p[205];
double d[205];
void Dijsktra(int s,int n)
{
int i,j,k;
bool visited[205]={false};
for(i=0;i<n;i++)
d[i]=a[s][i];
visited[s]=true;
d[s]=0;
while(k!=1)
{
double min=INF;
for(j=0;j<n;j++)
if(!visited[j]&&min>d[j])
{
min=d[j];
k=j;
}
visited[k]=true;
for(j=0;j<n;j++)
if(!visited[j]&&d[k]+a[k][j]<d[j])
d[j]=d[k]+a[k][j];
}
}
double get(int j,int k,int tag)
{
double result;
if(tag==0)
result=(sqrt(double((p[k].x-p[j].x)*(p[k].x-p[j].x)+(p[k].y-p[j].y)*(p[k].y-p[j].y)))/40000*60);//train
else result=(sqrt(double((p[k].x-p[j].x)*(p[k].x-p[j].x)+(p[k].y-p[j].y)*(p[k].y-p[j].y)))/10000*60);//walk
return result;
}
int main()
{
int i,j,count;
int x,y;
cin>>p[0].x>>p[0].y;
cin>>p[1].x>>p[1].y;
for(i=0;i<205;i++)
for(j=0;j<205;j++)
a[i][j]=0;
i=2;
count=2;
while(scanf("%d%d",&x,&y)!=EOF)//
{
if(x==-1&&y==-1)
{
for(j=count;j<i-1;j++)
a[j][j+1]=get(j,j+1,0);
count=i;
continue;
}
p[i].x=x,p[i].y=y;
i++;
}
for(i=0;i<count;i++)
{
for(j=0;j<count;j++)
{
if(a[i][j]==0&&i!=j)
a[i][j]=get(i,j,1);
}
}
Dijsktra(0,count);
cout<<fixed<<setprecision(0)<<d[1]<<endl;
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator