当前位置： 代码迷 >> 综合 >> 蓝桥杯 ALGO-25 VIP试题 Car的旅行路线 （试题解析）
  详细解决方案

蓝桥杯 ALGO-25 VIP试题 Car的旅行路线 （试题解析）

热度：35   发布时间：2024-01-21 20:11:53.0

试题 算法训练 Car的旅行路线

提交此题   评测记录  

资源限制

时间限制：1.0s   内存限制：256.0MB

问题描述

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

输入格式

　　的第一行有四个正整数s，t，A，B。
　　S表示城市的个数，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行，每行一个数据对应测试数据，保留一位小数。

样例输入

1
1 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

数据规模和约定

　　0<S<=100，

 

解题思路：传统的Dijkstra算法解题，只不过数据的初始化（初始化每条路径）比较繁琐，如何初始化（比如，已知矩形三点坐标 ，求第四点坐标。。。）思考时间长，代码量巨大。 把每个机场看做一个点，A城到B城最少费用，等价于，A城机场（择优四选一） 到 B城机场（择优四选一）最少的费用，先数据初始化，然后就是Dijkstra 算法遍历（共4轮）A城4个机场的B城的最少费用，最后四选一求最优值。

By the way，题目的样例输入的s错了，很明显应该是3 。还有样例输出也错了，题目的要求是保留一位小数，明显47.55错了，应该是47.5 。

 

代码如下：

#include <iostream>
#include <vector>
#include <cmath>
#include <string.h> 

using namespace std;

#define INF 65535

struct Airport{
    int x,y;
    int cityNO;
    int NO;
    Airport(){    }    
    Airport(int xx,int yy,int cn,int nn):x(xx),y(yy),cityNO(cn),NO(nn){    }
}AP[410];

struct Way{
    int V2;
    double W;
    Way(){    }
    Way(int vv,double ww):V2(vv),W(ww){    }
    
};
vector< vector<Way> >    G(410);
int s,t,A,B;
double dist[410];
int collected[410];

int cnt=1;

double getDist(Airport A1,Airport A2){
    double d=(A1.x-A2.x)*(A1.x-A2.x)+(A1.y-A2.y)*(A1.y-A2.y);
    return sqrt(d);
    
}

Airport add4thAP(Airport A1,Airport A2,Airport A3){    //找第四个机场坐标
    double D12=getDist(A1,A2);
    double D13=getDist(A1,A3);
    double D23=getDist(A2,A3);
    if(D12>D13 && D12>D23){// D12 为直角三角形的斜边 
        int cx=A1.x+A2.x;
        int cy=A1.y+A2.y;
        int x4=cx-A3.x;
        int y4=cy-A3.y;
        Airport A4(x4,y4,A1.cityNO,cnt++);
        return A4;

    }
    if(D13>D12 && D13>D23){//D13 为直角三角形的斜边 
        int cx=A1.x+A3.x;
        int cy=A1.y+A3.y;
        int x4=cx-A2.x;
        int y4=cy-A2.y;
        Airport A4(x4,y4,A1.cityNO,cnt++);
        return A4;
    }
    if(D23>D12 && D23>D13){//D23 为直角三角形的斜边 
        int cx=A2.x+A3.x;
        int cy=A2.y+A3.y;
        int x4=cx-A1.x;
        int y4=cy-A1.y;
        Airport A4(x4,y4,A1.cityNO,cnt++);
        return A4;
    }
    
}

void linkWayInCity(Airport A1,Airport A2,Airport A3,Airport A4,int Ti){
    //1、以为起点A1向其他三点 建路
    G[A1.NO].push_back(Way(A2.NO,Ti*getDist(A1,A2))); 
    G[A1.NO].push_back(Way(A3.NO,Ti*getDist(A1,A3) ));
    G[A1.NO].push_back(Way(A4.NO,Ti*getDist(A1,A4) ));
    
    G[A2.NO].push_back(Way(A1.NO,Ti*getDist(A2,A1) ));
    G[A2.NO].push_back(Way(A3.NO,Ti*getDist(A2,A3) ));
    G[A2.NO].push_back(Way(A4.NO,Ti*getDist(A2,A4) ));
    
    G[A3.NO].push_back(Way(A1.NO,Ti*getDist(A3,A1) ));
    G[A3.NO].push_back(Way(A2.NO,Ti*getDist(A3,A2) ));
    G[A3.NO].push_back(Way(A4.NO,Ti*getDist(A4,A3) ));
    
    G[A4.NO].push_back(Way(A1.NO,Ti*getDist(A1,A4) ));
    G[A4.NO].push_back(Way(A2.NO,Ti*getDist(A2,A4) ));
    G[A4.NO].push_back(Way(A3.NO,Ti*getDist(A4,A3) ));
    
}
void ReadInput(){
    cin>>s>>t>>A>>B;
    
    
    for(int i=1;i<=s;i++){
        int xi1,yi1,xi2,yi2,xi3,yi3,Ti;
        cin>>xi1>>yi1>>xi2>>yi2>>xi3>>yi3>>Ti;
        
        Airport A1(xi1,yi1,i,cnt++);
        AP[A1.NO]=A1;
        
        
        Airport A2(xi2,yi2,i,cnt++);
        AP[A2.NO]=A2;
    
        
        Airport A3(xi3,yi3,i,cnt++);
        AP[A3.NO]=A3;
        
        Airport A4=add4thAP(A1,A2,A3);
        AP[A4.NO]=A4;
        
        if(i!=A && i!=B)
            linkWayInCity(A1,A2,A3,A4,Ti);
        
    }
}

void addAirWay(int city,int pos){
    int curNO=(city-1)*4;
    int curPos=(pos-1)*4;
    
    G[curNO+1].push_back(Way(curPos+1,t*getDist(AP[curNO+1],AP[curPos+1])));
    G[curNO+1].push_back(Way(curPos+2,t*getDist(AP[curNO+1],AP[curPos+2])));
    G[curNO+1].push_back(Way(curPos+3,t*getDist(AP[curNO+1],AP[curPos+3])));
    G[curNO+1].push_back(Way(curPos+4,t*getDist(AP[curNO+1],AP[curPos+4])));
    
    G[curNO+2].push_back(Way(curPos+1,t*getDist(AP[curNO+2],AP[curPos+1])));
    G[curNO+2].push_back(Way(curPos+2,t*getDist(AP[curNO+2],AP[curPos+2])));
    G[curNO+2].push_back(Way(curPos+3,t*getDist(AP[curNO+2],AP[curPos+3])));
    G[curNO+2].push_back(Way(curPos+4,t*getDist(AP[curNO+2],AP[curPos+4])));
    
    G[curNO+3].push_back(Way(curPos+1,t*getDist(AP[curNO+3],AP[curPos+1])));
    G[curNO+3].push_back(Way(curPos+2,t*getDist(AP[curNO+3],AP[curPos+2])));
    G[curNO+3].push_back(Way(curPos+3,t*getDist(AP[curNO+3],AP[curPos+3])));
    G[curNO+3].push_back(Way(curPos+4,t*getDist(AP[curNO+3],AP[curPos+4])));
    
    G[curNO+4].push_back(Way(curPos+1,t*getDist(AP[curNO+4],AP[curPos+1])));
    G[curNO+4].push_back(Way(curPos+2,t*getDist(AP[curNO+4],AP[curPos+2])));
    G[curNO+4].push_back(Way(curPos+3,t*getDist(AP[curNO+4],AP[curPos+3])));
    G[curNO+4].push_back(Way(curPos+4,t*getDist(AP[curNO+4],AP[curPos+4])));
    
    
}

void initAirWay(){
    
    for(int i=1;i<=s;i++){
        for(int j=1;j<=s;j++){
            if(j!=i  ){
                addAirWay(i,j);
            }
        }
    }
    

    
        
}

int findMinDist(int NO){
    double thismin=INF;
    int pos=-1;
    for(int i=0;i<G[NO].size();i++){
        int next=G[NO][i].V2;
        double curW=G[NO][i].W;
        if( collected[next]==0 && curW<thismin){
            thismin=curW;
            pos=next;
        }
    }
    return pos;
}

double Dijkstra(int ANO){
    //初始化dist 
    for(int i=1;i<s*4;i++){
        if(i<(A-1)*4+1 && i>(A*4) ){
            dist[i]=INF;
        }
        else{
            dist[i]=0;
        }    
    }
    memset(collected,0,sizeof(collected));
    
    for(int i=0;i<G[ANO].size();i++){
        int next=G[ANO][i].V2;
        dist[next]=G[ANO][i].W;
    }
    
    while(1){
        int V=findMinDist(ANO);
        if(V==-1)
            break;
        collected[V]=1;
        for(int i=0;i<G[V].size();i++){
            int V2=G[V][i].V2;
            
                if(dist[V]+G[V][i].W<dist[V2]){
                    dist[V2]=dist[V]+G[V][i].W;
                    //collected[V2]=1;
                }
            
        }
    }
    
    double res=min( min(dist[(B-1)*4+1],dist[(B-1)*4+2]),min(dist[(B-1)*4+3],dist[B*4] ));
    return res;
}

int main(int argc, char** argv) {
    ReadInput();
    if(A==B){
        cout<<"0.0"<<endl;
    }
    else{
        initAirWay();
        double D1=Dijkstra( A*4-3 );
        double D2=Dijkstra( A*4-2 );
        double D3=Dijkstra( A*4-1 );
        double D4=Dijkstra( A*4 );
    
        double res=min( min(D1,D2),min(D3,D4)  );
    
        printf("%0.1lf\n",res);
    }
    
//    cout<<res<<endl;
//    for(int i=1;i<=s*4;i++){
//        cout<<"机场坐标：("<<AP[i].x<<","<<AP[i].y<<")  city:"<<AP[i].cityNO<<endl;
//    }


    return 0;
}

  相关解决方案

代码迷 - 您身边的软件异常，代码异常，编程异常助手（发现，解决，分享）
Copyright © 2009-2013 DAIMAMI.COM. All rights reserved.