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

Car的旅行路线 分数:

最短路径问题

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 ;
}