[p1027]Car的旅行路线
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 <iostream>
#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);
}
}