蓝桥杯-Car的旅行路线

链接地址: http://ayit.acmclub.com/index.php?app=problem_title&id=233&problem_id=21476

 

Car的旅行路线 分数:

时间限制：1 秒

内存限制：128 兆

特殊判题： 否

提交：2

解决： 1

题目描述

　　又到暑假了，住在城市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个城市高速铁路单位里程的价格。

数据规模和约定
　　0<S<=100，

输出

　　共有n行，每行一个数据对应测试数据，保留一位小数。

样例输入

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

 

 

最短路径问题

1）算出每个城市的第四个飞机场坐标

2）计算出4×s个点，每两个点的费用

3）Dijkstra算法找最短路

 

#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>

using namespace std ;

#define MAXN 405
#define INF 1e9

struct Point {
    int x , y ;
    Point( int x = 0 , int y = 0 ):x(x),y(y){}
};
Point data[105][4] ;    //城市飞机场的点坐标
int charge[105] ;      //高速公路的费用

Point counter( const Point &a , const Point &b , const Point &c ) { //计算矩形第四个点
     Point ab( b.x-a.x , b.y-a.y ) ;
     Point ac( c.x-a.x , c.y-a.y ) ;
     if( ab.x*ac.x + ab.y*ac.y == 0 ) return Point( b.x+c.x-a.x , b.y+c.y-a.y ) ;
     return counter( c , a , b ) ;
}

double counter( const Point &a , const Point &b ) { //计算两点的距离
    return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) ) ;
}

struct Edge {
    int to ;
    double dist ;
    Edge( int to , double dist ):to(to),dist(dist){}
};

struct Node {
    double dist ; //到此点的距离
    int num ;    //点的编号
    Node( int num , double dist ):dist(dist),num(num){}
    bool operator < ( const Node & n ) const {  //小顶堆
        return dist > n.dist ;
    }
};

struct Dijkstra {
    int n ;   //点数
    vector<Edge> edges ; //边列表
    vector<int> G[MAXN] ; //存图
    double d[MAXN] ; //存放结果（费用）

    void init( int n ) {
        this->n = n ;
        for( int i = 1 ; i <= n ; i ++ ) {  //从1开始计数
            G[i].clear() ;
        }
        edges.clear() ;
    }

    void AddEdge( int from , int to , double dist ) {  //注意是有向图
        edges.push_back( Edge(to,dist) ) ;
        G[from].push_back( edges.size()-1 ) ;
    }

    void dijkstra( int s ) { //计算S点到所有点的距离
        for( int i = 1 ; i <= n ; i ++ ) d[i] = INF ; d[s] = 0.0 ;
        bool done[MAXN] ; memset( done , false , sizeof( done ) ) ;
        priority_queue<Node> pq ; pq.push( Node( s , 0.0 ) ) ;
        while( !pq.empty() ) {
            int u = pq.top().num ; pq.pop() ;
            if( done[u] ) continue ;
            done[u] = true ;
            for( int i = 0 ; i < G[u].size() ; i ++ ) {
                int v = edges[ G[u][i] ].to ;
                double dist = edges[ G[u][i] ].dist ;
                if( d[v] > d[u] + dist ) {
                    d[v] = d[u] + dist ;
                    pq.push( Node( v , d[v] ) ) ;
                }
            }
        }
    }

}AC;


int main() {

    int s , t , A , B ; scanf("%d%d%d%d" , &s , &t , &A , &B ) ;

    for( int i = 1 ; i <= s ; i ++ ) {   //输入数据
        for( int j = 0 ; j < 3 ; j ++ ) {
            scanf("%d%d" , &data[i][j].x , & data[i][j].y ) ;
        }
        scanf("%d" , &charge[i] ) ;
    }

    for( int i = 1 ; i <= s ; i ++ ) {  //计算第四个点
        data[i][3] = counter( data[i][0] , data[i][1] , data[i][2] ) ;
    }

    AC.init(MAXN) ;  //存图
    int n = 4*s ;
    int a_col , a_row , b_col , b_row ;
    for( int i = 0 ; i < n ; i ++ ) { //0，1，2，3为一号城市，以此类推
        a_row = i / 4 + 1 ; a_col = i % 4 ;
        for( int j = 0 ; j < n ; j ++ ) if( i != j ) { //计算任意两个点的距离
            b_row = j / 4 + 1 ; b_col = j % 4 ;
            double dist = counter( data[a_row][a_col] , data[b_row][b_col] ) ;
            if( a_row == b_row ) { //如果两个点在同一个城市，则走高速
                AC.AddEdge( i+1 , j+1 , dist*charge[a_row] ) ;
                AC.AddEdge( j+1 , i+1 , dist*charge[a_row] ) ;
            }
            else {
                AC.AddEdge( i+1 , j+1 , dist*t ) ;
                AC.AddEdge( j+1 , i+1 , dist*t ) ;
            }
        }
    }

    double res = INF ;
    for( int i = 4*(A-1)+1 ; i < 4*A+1 ; i ++ ) {  //A点的任意一个机场
        AC.dijkstra( i ) ;
        for( int j = 4*(B-1)+1 ; j < 4*B+1 ; j ++) { //B点的任意一个机场
            if( res > AC.d[j] ) res = AC.d[j] ;
        }
    }
    printf("%.1lf\n" , res ) ;

    return 0 ;
}