P1027 Car的旅行路线

题目描述

又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。

图例（从上而下）

机场 高速铁路

飞机航线

注意：图中并没有标出所有的铁路与航线。

那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。

找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。

输入输出格式

输入格式：

第一行为一个正整数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行，每行一个数据对应测试数据。 保留一位小数

输入输出样例

输入样例#1：

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

输出样例#1：

47.5 #分析

####披着蓝皮的大水题

每一个机场看作一个节点，所有道路和航线看成边，边权为距离×价格，跑一遍floyd后，枚举起点城市终点城市的所有机场判断最小价格即可。 #include

#include <cmath>
#include <cstdio>
#define INF 999999999
using namespace std;
int nce = 0;
int ncity,op,ed;
double fp;
double ans = INF;
struct City{
    double ft;
    double x[4];
    double y[4];
}c [105];
double e[105][4][105][4];
double mymin(double a,double b)
{
    if(a < b)
    {
        return a;
    }
    return b;
}
double d(double x1,double y1,double x2,double y2)
{
    return sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1));
}
bool is90(double x1,double y1,double x2,double y2,double x3,double y3)
{
    if((x2-x1) * (x3-x2) + (y2-y1) * (y3-y2) == 0)
    {
        return true;
    }
    return false;
}
int main()
{
    cin >> nce;
    for(int ncc = 0;ncc < nce;ncc++)
    {
        for(int i = 0;i < 105;i++)
        {
            for(int j = 0;j < 4;j++)
            {
                for(int k = 0;k < 105;k++)
                {
                    for(int l = 0;l < 4;l++)
                    {
                        e[i][j][k][l] = INF;
                    }
                }
            }
        }
        cin >> ncity >> fp >> op >> ed;
        for(int i = 0;i < ncity;i++)
        {
            for(int j = 0;j < 3;j++)
            {
                cin >> c[i].x[j] >> c[i].y[j];
            }
            cin >> c[i].ft;
        }
        //get the forth point (Vector)
        for(int i = 0;i < ncity;i++)
        {
            double midx,midy;
            if(is90(c[i].x[0],c[i].y[0],c[i].x[1],c[i].y[1],c[i].x[2],c[i].y[2]))
            {
                midx = (c[i].x[0] + c[i].x[2]) / 2;
                midy = (c[i].y[0] + c[i].y[2]) / 2;
                c[i].x[3] = 2*midx - c[i].x[1];
                c[i].y[3] = 2*midy - c[i].y[1];
            }else if(is90(c[i].x[1],c[i].y[1],c[i].x[0],c[i].y[0],c[i].x[2],c[i].y[2]))
            {
                midx = (c[i].x[1] + c[i].x[2]) / 2;
                midy = (c[i].y[1] + c[i].y[2]) / 2;
                c[i].x[3] = 2*midx - c[i].x[0];
                c[i].y[3] = 2*midy - c[i].y[0];
            }else if(is90(c[i].x[0],c[i].y[0],c[i].x[2],c[i].y[2],c[i].x[1],c[i].y[1]))
            {
                midx = (c[i].x[0] + c[i].x[1]) / 2;
                midy = (c[i].y[0] + c[i].y[1]) / 2;
                c[i].x[3] = 2*midx - c[i].x[2];
                c[i].y[3] = 2*midy - c[i].y[2];
            }
            //cout << c[i].x[3] << " " <<  c[i].y[3] << endl;
        }
        //init
        for(int ic = 0;ic < ncity;ic++)
        {
            for(int ip = 0;ip < 4;ip++)
            {
                for(int jc = 0;jc < ncity;jc++)
                {
                    for(int jp = 0;jp < 4;jp++)
                    {
                        if(ic == jc)
                        {
                            if(jp == ip)
                            {
                                e[ic][ip][jc][jp] = 0;
                            }else{
                                e[ic][ip][jc][jp] = c[ic].ft * d(c[ic].x[ip],c[ic].y[ip],c[jc].x[jp],c[jc].y[jp]);
                            }
                        }else{
                            e[ic][ip][jc][jp] = fp * d(c[ic].x[ip],c[ic].y[ip],c[jc].x[jp],c[jc].y[jp]);
                        }
                        //cout << e[ic][ip][jc][jp] << endl;
                    }
                }
            }
        }
        //floyd
        for(int kc = 0;kc < ncity;kc++)
        {
            for(int kp = 0;kp < 4;kp++)
            {
                for(int ic = 0;ic < ncity;ic++)
                {
                    for(int ip = 0;ip < 4;ip++)
                    {
                        for(int jc = 0;jc < ncity;jc++)
                        {
                            for(int jp = 0;jp < 4;jp++)
                            {
                                e[ic][ip][jc][jp] = mymin(e[ic][ip][jc][jp],e[ic][ip][kc][kp] + e[kc][kp][jc][jp]);
                            }
                        }
                    }
                }
            }
        }
        for(int oi = 0;oi < 4;oi++)
        {
            for(int ei = 0;ei < 4;ei++)
            {
                ans = mymin(ans,e[op-1][oi][ed-1][ei]);
            }
        }
        printf("%.1lf\n",ans);
    }
}