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