首页
社区
课程
招聘
跪求修正!NOIP2001Car的旅行计划
发表于: 2011-8-20 15:36 4026

跪求修正!NOIP2001Car的旅行计划

2011-8-20 15:36
4026
题目描述
又到暑假了,住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场,分别位于一个矩形的四个顶点上,同一个城市中两个机场之间有一条笔直的高速铁路,第I个城市中高速铁路了的单位里程价格为Ti,任意两个不同城市的机场之间均有航线,所有航线单位里程的价格均为t。
标出所有的铁路与航线。
那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题,于是她来向你请教。
任务
找出一条从城市A到B的旅游路线,出发和到达城市中的机场可以任意选取,要求总的花费最少。

输出:到屏幕(输出最小费用,小数点后保留2位。)

输入格式
第一行为一个正整数n(0<=n<=10),表示有n组测试数据。
每组的第一行有四个正整数s,t,A,B。
S(0<S<=100)表示城市的个数,t表示飞机单位里程的价格,A,B分别为城市A,B的序号,(1<=A,B<=S)。
接下来有S行,其中第I行均有7个正整数xi1,yi1,xi2,yi2,xi3,yi3,Ti,这当中的(xi1,yi1),(xi2,yi2),(xi3,yi3)分别是第I个城市中任意三个机场的坐标,T I为第I个城市高速铁路单位里程的价格。

输出格式
共有n行,每行一个数据对应测试数据。(小数点保留2位)[RQ已经订正本题目]

样例输入
1
3 10 1 3
1 1 1 3 3 1 30
2 5 7 4 5 2 1
8 6 8 8 11 6 3
样例输出
47.55

#include <iostream>
#include <string>
#include <math.h>
#define MAXN 105
#define MAXM 550
#define MAX 9999999.999



typedef struct point p;

double map[MAXM][MAXM];


struct point
{
  double x,y;   
};
       
struct node
{
       p *a;
       p *b;
       p *c;
       p *d;
       
       double T;//用来表示这里地铁每单位距离的价格 
}citys[MAXN];
       

p* qD(p* a,p* b,p* c) //用来求第四个点 
{
       struct point *p4;
       p4 = (struct point *)malloc(sizeof(struct point));
       double x4,y4;
       double centerX,centerY; 
       //求出三点的向量 
       double xAB = a->x - b->x;
       double yAB = a->y - b->y;
       double xAC = a->x - c->x;
       double yAC = a->y - c->y;
       double xBC = b->x - c->x;
       double yBC = b->y - c->y;
       if(xAB * xAC + yAB * yAC == 0)
       {
                     centerX = b->x+c->x;
                     centerY = b->y+c->y;
                     
                     x4 = centerX - a->x;
                     y4 = centerY - a->y;
       } 
       else if(xAB * xBC + yAB * yBC == 0)
       {
                     centerX = a->x+c->x;
                     centerY = a->y+c->y;
                     
                     x4 = centerX - b->x;
                     y4 = centerY - b->y;    
       }
       else if(xAC * xBC + yAC * yBC== 0)
       {
                     centerX = a->x+b->x;
                     centerY = a->y+b->y;
                     
                     x4 = centerX - c->x;
                     y4 = centerY - c->y;
       }
       else 
       {
            printf("Creat Point ERROR!!!");
            exit(-1);     
       }
       
       p4->x = x4;
       p4->y = y4;
       return p4;
       
}

double moneyWast(p *a,p* b,double T)
{
      return T*sqrt(pow((a->x - b->x),2)+ pow((a->y - b->y),2));
}


void doIt(int s,double t,int A,int B)
{
     int i,j,k;
     double x1,y1,x2,y2,x3,y3,x4,y4;

     int shangOne,shangTwo,ysOne,ysTwo;
     int cur;
     double min = MAX;
     struct point *pp1,*pp2;
     double T;//存价格 
     for(i=1;i <= s;i ++)
     {
               scanf("%lf %lf %lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&x3,&y3,&T);
               citys[i].a = (struct point *)malloc(sizeof(struct point));
               citys[i].b = (struct point *)malloc(sizeof(struct point));
               citys[i].c = (struct point *)malloc(sizeof(struct point));
               citys[i].a->x = x1;
               citys[i].a->y = y1;
               citys[i].b->x = x2;
               citys[i].b->y = y2;
               citys[i].c->x = x3;
               citys[i].c->y = y3;
               citys[i].d = qD(citys[i].a,citys[i].b,citys[i].c);
               citys[i].T = T;
     }
     
      
      for(i=1;i <= s*4;i ++)
      {
                for(j=1;j <= s*4;j ++)
                {
                          if(i == j) 
                          {
                               map[i][j] = 0;     
                          }         
                          else
                          {
                               shangOne = i/4+1;
                               shangTwo = j/4+1;
                               ysOne = i%4;
                               ysTwo = j%4;
                               
                               if(ysOne == 0)
                               {
                                        shangOne --;
                                        ysOne = 4;
                               }
                               if(ysTwo == 0)
                               {
                                        shangTwo --;
                                        ysTwo = 4;         
                               }
                               switch(ysOne)
                               {
                                            case 1:
                                                 pp1 = citys[shangOne].a;
                                                 break;
                                            case 2:
                                                 pp1 = citys[shangOne].b;
                                                 break;
                                            case 3:
                                                 pp1 = citys[shangOne].c;
                                            case 4:
                                                 pp1 = citys[shangOne].d;
                                                 break; 
                                            default:
                                                 printf("ERROR!!");
                                                 break;       
                               }
                               switch(ysTwo)
                               {
                                            case 1:
                                                 pp2 = citys[shangTwo].a;
                                                 break;
                                            case 2:
                                                 pp2 = citys[shangTwo].b;
                                                 break;
                                            case 3:
                                                 pp2 = citys[shangTwo].c;
                                                 break;
                                            case 4:
                                                 pp2 = citys[shangTwo].d;
                                                 break;
                                            default:
                                                 printf("ERROR!!");
                                                 break;             
                               }        
                               
                               if(shangOne == shangTwo)//说明他们两个在同一个城市里可以坐火车到达 
                               {
                                           map[i][j] = moneyWast(pp1,pp2,citys[shangOne].T);

                               }
                               else//坐飞机到达 
                               {
                                            map[i][j] = moneyWast(pp1,pp2,t);
                               }
                          }
                }          
      }

      //Floyd
      for(k=1;k <= s*4;k ++)
      {
                for(i=1;i <= s*4;i ++)
                {
                          for(j=1;j <= s*4;j ++)
                          {
                                    if(i != j && i != k && j != k && map[i][j] > map[i][k] + map[k][j])
                                    {
                                                 map[i][j] = map[i][k] + map[k][j];             
                                    }
                               
                          }                    
                }
      }
      
      //选出最小的费用
      
      for(i=A*4-3;i <= A*4;i ++)
      {
                    for(j=B*4-3;j <= B*4;j ++)
                    {
                                  if(map[i][j] < min)
                                  {
                                               min = map[i][j];             
                                  }              
                    }              
      } 
                
      printf("%0.1lf\n",min);
}



int main()
{
    freopen("Test.in","r",stdin);
    freopen("Test.out","w",stdout);
    int i;
    int n;
    int s,A,B;
    double t;
    scanf("%d",&n);
    for(i=1;i <= n;i ++)
    {
             scanf("%d %lf %d %d",&s,&t,&A,&B);    
             doIt(s,t,A,B);   
    }
}


可以过4个点,一共是5个点
样例数据就是过不了,最后一个点的答案也是错误的
求解啊!!!各位大牛!!

[招生]科锐逆向工程师培训(2024年11月15日实地,远程教学同时开班, 第51期)

收藏
免费 1
支持
分享
最新回复 (5)
雪    币: 1149
活跃值: (888)
能力值: ( LV13,RANK:260 )
在线值:
发帖
回帖
粉丝
2
我要把题目给读懂.....   好了 应该差不多要动了....好久不看算法,感觉都没了....
2011-8-20 17:28
0
雪    币: 788
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
                                switch(ysOne)
                               {
                                            case 1:
                                                 pp1 = citys[shangOne].a;
                                                 break;
                                            case 2:
                                                 pp1 = citys[shangOne].b;
                                                 break;
                                            case 3:
                                                 pp1 = citys[shangOne].c;
                                                 break;//[COLOR="Red"]你这里少了break!!!!!!!!!!!![/COLOR]
                                            case 4:
                                                 pp1 = citys[shangOne].d;
                                                 break; 
                                            default:
                                                 printf("ERROR!!");
                                                 break;       
                               }
2011-8-21 09:36
0
雪    币: 788
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
4
如果你习惯了下标从0开始,这个代码可以简单很多

连通是双向的矩阵是对称的,可以让构造map的循环可以少跑几次

for(i=1;i <= s*4;i ++)
{
for(j=i;j <= s*4;j ++)
{
... ...
if(shangOne == shangTwo)//说明他们两个在同一个城市里可以坐火车到达
{
map[j] = moneyWast(pp1,pp2,citys[shangOne].T);

}
else//坐飞机到达
{
map[j] = moneyWast(pp1,pp2,t);
}
map[j] = map[j];
}
}
2011-8-21 09:42
0
雪    币: 92
活跃值: (16)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
5
此题楼主的代码稍微修改一下就可以 AC..

附图:

题目图片:

修改地方: 1) 去掉 exit(-1);
2) switch case漏了 Break;
3) malloc 需要加上 stdlib.h头文件
4) scanf 和 printf 需要加上 cstdio  或者 stdio.h 头文件
2011-8-21 09:59
0
雪    币: 36
活跃值: (588)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
6
确实是break的问题,已经解决了
谢谢各位回答~~~~~
跪谢~~!!
2011-8-21 13:51
0
游客
登录 | 注册 方可回帖
返回
//