http://poj.org/problem?id=2502
这题本来应该用迪杰斯特拉做的 ,因为想试试弗洛伊德所以就试试 谁知道代码一一直wrong ,路过的麻烦指点一下
代码一: #include<stdio.h> #include<math.h> struct node { double x; double y; }node[205]; double dis[205][205]; double cal(struct node a,struct node b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int main() { int i,j,k,v,u; scanf("%lf%lf%lf%lf",&node[0].x,&node[0].y,&node[1].x,&node[1].y); dis[0][1]=dis[1][0]=cal(node[0],node[1]); i=2; while(scanf("%lf%lf",&node[i].x,&node[i].y)!=EOF) { if((node[i].x==-1&&node[i].y==-1)) { for(j=0;j<i;++j) dis[j][j+1]=dis[j+1][j]=0.25*dis[j][j+1]; continue; } for(j=0;j<i;++j) dis[i][j]=dis[j][i]=cal(node[j],node[i]); ++i; } for(k=0;k<i;++k) for(v=0;v<i;++v) for(u=0;u<i;++u) if(dis[v][k]&&dis[u][k]) { if(dis[v][u]>dis[v][k]+dis[k][u]) dis[v][u]=dis[v][k]+dis[k][u]; } printf("%.2f\n",0.006*dis[0][1]); return 0; }//wrong answer 不知道错在哪,路过的指点一下? /* 代码二: #include<stdio.h> #include<stdlib.h> #include<math.h> #include<string.h> typedef struct point { double x,y; } Point; Point p[205]; double dis[205][205]; double distance(Point a,Point b);//计算两点间距离 double floyd(int tot); int main() { double ax,bx; int i,j,k,stop; memset(dis,0,sizeof(dis)); scanf("%lf%lf%lf%lf",&p[0].x,&p[0].y,&p[1].x,&p[1].y); dis[0][1] = dis[1][0] = distance(p[0],p[1]); i = 2; while(1) { if(scanf("%lf%lf",&ax,&bx) != 2) break; k = i ; do { p[i].x = ax ; p[i].y = bx ; for(j = 0 ; j < i ; ++j)//计算新的点到其余各点的距离 dis[i][j] = dis[j][i] = distance(p[i],p[j]); ++i; }while(scanf("%lf%lf",&ax,&bx)&&(ax != -1 || bx != -1)); for(j = k ; j < i-1 ; ++j)//地铁,距离缩小4倍,因为速度快4倍 dis[j][j+1] = dis[j+1][j] = distance(p[j],p[j+1])*0.25; } stop = i; printf("%.0lf\n",0.006*floyd(stop)); //换算成时间 //system("pause"); return 0; } double floyd(int tot) { int i,j,k; double t; for(k = 0 ; k < tot ; ++k) for(i = 0 ; i < tot ; ++i) for(j = 0 ; j < tot ; ++j) { if(dis[i][k] && dis[k][j]) { t = dis[i][k] + dis[k][j]; if(t < dis[i][j]) dis[i][j] = t; } } return dis[0][1]; } double distance(Point a,Point b) { return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } //别人的AC代码 */