| ||||||||||
| 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 ,附上AC代码#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define inf 1<<22
using namespace std;
int used[550];
double dis[550];
double map[550][550];
int t;
struct point
{
double x,y;
}p[550];
void dijkstra()
{
memset(used,0,sizeof(used));
for(int i=1;i<t;i++)
dis[i]=map[0][i];
dis[0]=0;
used[0]=1;
int k;
double minn;
for(int i=1;i<t;i++)
{
minn=inf;
for(int j=1;j<t;j++)
{
if(!used[j]&&dis[j]<minn)
{
minn=dis[j];
k=j;
}
}
used[k]=1;
for(int j=1;j<t;j++)
{
if(!used[j]&&dis[j]>dis[k]+map[k][j])
dis[j]=map[k][j]+dis[k];
}
}
cout<<int(60.0*dis[1]+0.5)<<endl;//四舍五入
}
double d(double x1,double y1,double x2,double y2)
{
double temp=sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
return temp;
}
int main()
{
t=2;
int flag=0;
cin>>p[0].x>>p[0].y>>p[1].x>>p[1].y;
memset(map,0.0,sizeof(map));
while(cin>>p[t].x>>p[t].y)
{
if(p[t].x==-1&&p[t].y==-1)
{
flag=0;
continue;
}
if(flag)
{
double temp=d(p[t].x,p[t].y,p[t-1].x,p[t-1].y)/40000.0;
map[t][t-1]=map[t-1][t]=temp;
}
flag=1;
t++;
}
for(int i=0;i!=t;i++)
for(int j=0;j!=t;j++)
{
if(i!=j&&map[i][j]==0.0)
map[i][j]=map[j][i]=d(p[i].x,p[i].y,p[j].x,p[j].y)/10000.0;
}
dijkstra();
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator