首页
社区
课程
招聘
POJ2052 FLOYD算法解决,WRONG到吐了
发表于: 2011-10-5 16:17 5797

POJ2052 FLOYD算法解决,WRONG到吐了

2011-10-5 16:17
5797
题目地址:http://poj.org/problem?id=2502

题意:
你从家往学校赶,可以用步行和乘坐地铁这两种方式,步行速度为10km/h,乘坐地铁的速度为40KM/h。输入数据的第一行数据会给你起点和终点的x和y的坐标。然后会给你数目不超过200的双向地铁线路的站点,你可以从一个站点乘坐地铁到下一个站点,你可以在同一线路上乘坐地铁经过不同的站点,在不同线路的站点之间,你只能用步行的方式。让你求利用你可以利用的方式,求解到校花费的最短时间。

我是用floyd算法解决的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <math.h>
#define MAXN 205
#define MAX 999999

struct node
{
       int line; //-1 suggest that this is start point,-2 refer to end point
       int x,y;
}NODE[MAXN];

int nowPoint = 1;
double map[MAXN][MAXN];

void createNode(int line,int x,int y)
{
     NODE[nowPoint].line = line;
     NODE[nowPoint].x = x;
     NODE[nowPoint].y = y;
     nowPoint ++;
}


int main()
{    
    double ls;
    int i,j,k;
    int sX,sY,eX,eY;
    int stopX,stopY;
    scanf("%d %d %d %d",&sX,&sY,&eX,&eY);
    createNode(-1,sX,sY);
    createNode(-2,eX,eY); //先创建1,2下标为起点和重点 
    int lineNumber = 1;
    
    while(scanf("%d %d",&stopX,&stopY) != EOF)
    {
                    if(stopX == -1 && stopY == -1)
                    {
                             lineNumber ++;         
                    }
                    else
                    {
                             createNode(lineNumber,stopX,stopY);
                    }
                             
    }
     //建图
    for(i = 1;i < nowPoint;i ++)
    {
          for(j = 1;j < nowPoint;j ++)      
          {
                if(i == j)
                {
                     map[i][j] = 0.0;     
                }      
                else if(i != j && map[i][j] == 0.0)
                {
                     if(NODE[i].line == NODE[j].line)//一条线上的,坐地铁到达 
                     {
                                     ls = (sqrt((double)((NODE[i].x-NODE[j].x)*(NODE[i].x-NODE[j].x)+(NODE[i].y-NODE[j].y)*(NODE[i].y-NODE[j].y))))/4000*6;
                                     map[i][j] = ls;
                                     map[j][i] = ls;      
                     }
                     else //步行到达 
                     {
                                     ls = (sqrt((double)((NODE[i].x-NODE[j].x)*(NODE[i].x-NODE[j].x)+(NODE[i].y-NODE[j].y)*(NODE[i].y-NODE[j].y))))/1000*6;
                                     map[i][j] = ls;
                                     map[j][i] = ls;
                     }
                }
          }
    } 
   
   //floyd
   for(k = 1;k < nowPoint;k ++)
   {
           for(i = 1;i < nowPoint;i ++)
           {
                 if(i != k)
                 {
                      for(j = 1;j < nowPoint;j ++)
                      {
                            if(i != j)
                            {
                                    if(map[i][j] > map[i][k] + map[k][j])
                                    {
                                                 map[i][j] = map[i][k] + map[k][j];             
                                    }     
                            }
                      }     
                 }
     
           }      
   }
   
   printf("%d",(int)map[1][2]); 
   return 0;
}


只找到一组测试数据,测试错了,但就是不知道错在哪里
1 1 10001 10001
2777 886 7793 6915 5386 8335 6649 492 2362 1421 8690 27 7763 59 540 3926 9172 3426 5211 5736 2567 5368 5782 6429 2862 1530 4067 5123 3929 3135 4022 9802 3069 3058 1393 8167 5011 8456 6229 8042 4421 7373 3784 4919 5198 8537 8315 4324 6413 4370 6091 3526 9956 8980 6862 1873 6996 9170 2305 7281 7084 925 336 6327 846 6505 1313 1729 6124 5857 9582 3895 8814 545 5434 3367 4043 364 1087 3750 7276 6808 5788 7178 5403 3584 2754 2651 9932 2399 9676 5060 7739 3368 6226 12 8094 8586 795 7539 1434 570 7467 378 97 6601 3317 2902 6652 492 7301 756 4286 280 3865 9441 8444 9689 8440 6619 8031 4729 8097 8117 4481 5771 709 675 4567 8927 9497 7856 4586 2353 5306 6965 6219 4683 1528 8624 5732 2871 9503 8829 8270 19 9708 3368 6340 6715 7796 8149 2618 723 2846 2245 2921 3451 2379 3555 7764 7488 9841 8228 5193 2350 7034 1500 124 7764 6987 4914 3743 5856 2227 6491 9859 8365 1432 1936 6437 2551 3275 9228 1474 5407 8858 6121 6029 4395 8235 1237 5818 3793 6143 4428 5928 1011 8776 9529 4443 2404 4613 5763 8606 4538 2904 6840 5128 4818 7369 688 9917 7917 3324 6996 9470 7743 8490 2183 9772 5499 5644 6725 7505 5590 2954 8139 7669 9786 8542 8082 197 8464 9355 9507 6348 8804 3622 8611 9299 7828 5746 7343 4340 5568 3311 5422 7605 3810 5661 1801 4878 3730 9320 1305 9444 8736 8522 8626 6708 3465 8282 3416 2924 3258 2062 7637 2600 5624 3452 2036 9379 1899 7468 5550 973 71 3881 7131 8933 4930 8660 5894 7199 163 8899 7981 2959 2996 2813 3773 7190 9668 2926 1095 5084 6466 2090 1340 3376 7684 5936 5542 7445 9107 9179 9756 6887 8418 3348 9412 1659 2172 2336 2009 6342 5210 8206 7587 7713 9301 5321 7372 4819 1255 7721 4599 5939 9904 -1 -1
5667 3940 6228 1705 9150 1127 6658 5984 9224 3920 7269 2422 4081 1396 84 5630 1972 9292 3850 7672 5385 7625 9299 1222 6042 6640 713 3898 6190 2298 -1 -1
8209 2590 8819 8581 7732 9336 5994 1155 -1 -1
4769 379 1776 5273 7255 8850 8142 1860 5884 5579 3205 1993 -1 -1
2504 9567 1961 613 1326 2754 8944 4259 3202 8202 6784 3506 2842 2021 -1 -1
5189 9528 9908 8872 -1 -1

正确答案是36,我程序跑出来是29

跪求大虾帮忙找错,我在百度搜到了有人一样的错误,但是没提供解决办法
先跪谢!!!

[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

收藏
免费 0
支持
分享
最新回复 (6)
雪    币: 2676
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
2
                     if(NODE[i].line == NODE[j].line)//一条线上的,坐地铁到达 
                     {
                                     ls = (sqrt((double)((NODE[i].x-NODE[j].x)*(NODE[i].x-NODE[j].x)+(NODE[i].y-NODE[j].y)*(NODE[i].y-NODE[j].y))))/4000*6;
                                     map[i][j] = ls;
                                     map[j][i] = ls;      
                     }

题目没说在同一条线路上的任意两站都直达哦!
2011-10-5 18:17
0
雪    币: 36
活跃值: (598)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
3
[QUOTE=李晓岚;1006380]if(NODE[i].line == NODE[j].line)//一条线上的,坐地铁到达
                     {
                                     ls = (sqrt((double)((NODE[i].x-NODE[j].x)...[/QUOTE]

这是建图过程的代码,前面加了约束条件map[i][j] == 0.0,是为了加快效率,而且你从i到j,和从j到i的时间是一样的
2011-10-5 18:38
0
雪    币: 2676
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
4
我说的意思是,假如一条地铁线路经过三个站点,只能坐地铁从一号到二号,从二号到三号,而并不能直接从一号直接到三号。所以if(NODE[i].line == NODE[j].line)//一条线上的,坐地铁到达 ,而且是直接到达,不经过其它中间站点,这个判断条件是不对的。
2011-10-5 20:47
0
雪    币: 36
活跃值: (598)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
5
[QUOTE=李晓岚;1006435]我说的意思是,假如一条地铁线路经过三个站点,只能坐地铁从一号到二号,从二号到三号,而并不能直接从一号直接到三号。所以if(NODE[i].line == NODE[j].line)//一条线上的,坐地铁到达 ,而且是直接到达,不经过其它中间站点,这个判断条件是不对的。[/QUOTE]

确实是这个地方有问题,NODE[i].line == NODE[j].line && (i == j-1 ||i == j + 1)条件改成这个还是不行能帮忙修改下吗?我调了一天半,实在是不知道再怎么改了
跪谢!
2011-10-6 11:17
0
雪    币: 2676
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
6
[QUOTE=hzmslx;1006542]确实是这个地方有问题,NODE[i].line == NODE[j].line && (i == j-1 ||i == j + 1)条件改成这个还是不行能帮忙修改下吗?我调了一天半,实在是不知道再怎么改了
跪谢![/QUOTE]

printf("%d",(int)(map[1][2]+0.5)); 

需要round to nearest integer.
2011-10-6 11:24
0
雪    币: 36
活跃值: (598)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
7
[QUOTE=李晓岚;1006544]
printf("%d",(int)(map[1][2]+0.5)); 

需要round to nearest integer.[/QUOTE]

非常非常非常感谢!!!分给你了
最后输出   printf("%d",(int)(map[1][2]+0.5));  AC了

贴出完整代码给以后纠结这个问题的人参考
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <math.h>
#define MAXN 205
#define MAX 999999

struct node
{
       int line; //-1 suggest that this is start point,-2 refer to end point
       int x,y;
}NODE[MAXN];

int nowPoint = 1;
double map[MAXN][MAXN];

void createNode(int line,int x,int y)
{
     NODE[nowPoint].line = line;
     NODE[nowPoint].x = x;
     NODE[nowPoint].y = y;
     nowPoint ++;
}


int main()
{
    freopen("Test.in","r",stdin);
    freopen("Test.out","w",stdout);
    
    double ls;
    int i,j,k;
    int sX,sY,eX,eY;
    int stopX,stopY;
    scanf("%d %d %d %d",&sX,&sY,&eX,&eY);
    createNode(-1,sX,sY);
    createNode(-2,eX,eY); //先创建1,2下标为起点和重点 
    int lineNumber = 1;
    
    while(scanf("%d %d",&stopX,&stopY) != EOF)
    {
                    if(stopX == -1 && stopY == -1)
                    {
                             lineNumber ++;         
                    }
                    else
                    {
                             createNode(lineNumber,stopX,stopY);
                    }
                             
    }
    
     //建图
    for(i = 1;i < nowPoint;i ++)
    {
          for(j = 1;j < nowPoint;j ++)      
          {
                if(i == j)
                {
                     map[i][j] = 0.0;     
                }      
                else if(i != j && map[i][j] == 0.0)
                {
                     if(NODE[i].line == NODE[j].line && (i == j-1 ||i == j + 1))//一条线上的,坐地铁到达 
                     {
                                     ls = (sqrt((double)((NODE[i].x-NODE[j].x)*(NODE[i].x-NODE[j].x)+(NODE[i].y-NODE[j].y)*(NODE[i].y-NODE[j].y))))/4000*6.0;
                                     map[i][j] = ls;
                                     map[j][i] = ls;      
                     }
                     else //步行到达 
                     {
                                     ls = (sqrt((double)((NODE[i].x-NODE[j].x)*(NODE[i].x-NODE[j].x)+(NODE[i].y-NODE[j].y)*(NODE[i].y-NODE[j].y))))/1000*6.0;
                                     map[i][j] = ls;
                                     map[j][i] = ls;
                     }
                }
          }
    } 
   
   //floyd
   for(k = 1;k < nowPoint;k ++)
   {
           for(i = 1;i < nowPoint;i ++)
           {
                 if(i != k)
                 {
                      for(j = 1;j < nowPoint;j ++)
                      {
                            if(i != j)
                            {
                                    if(map[i][j] > map[i][k] + map[k][j])
                                    {
                                                 map[i][j] = map[i][k] + map[k][j];             
                                    }     
                            }
                      }     
                 }
     
           }      
   }
   
   printf("%d",(int)(map[1][2]+0.5)); 
   return 0;
}
2011-10-6 11:49
0
游客
登录 | 注册 方可回帖
返回
//