洛谷1027 Car的旅行路线[最短路]

题目描述

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

https://cdn.luogu.org/upload/pic/8.png
图片炸?http://cdn.luogu.org/upload/pic/8.png

图例(从上而下)
机场 高速铁路
飞机航线
  注意:图中并没有
标出所有的铁路与航线。
那么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

题解

求未知飞机场的坐标

由于每个城市都是矩形,所以每个城市中已知的三个飞机场必构成一个直角三角形,而未知的飞机场必在这个三角形的直角顶点的对点处。
求直角三角形的直角顶点可以求斜边,斜边两顶点外的那个点便是直角顶点。
而在平行四边形中,一条边的两个顶点的横(或纵)坐标的差值等于其对边两个顶点的横(或纵)坐标的差值。在求得直角顶点后,可以依此求得未知飞机场的坐标。

计算花费

飞机场编号如下:
City1:1 2 3 4
City2: 5 6 7 8
…… 由观察可知,飞机场编号(t)与城市编号(n)的关系为n=((t-1) div 4) +1.

Floyd处理

Floyd都会吧···
用完Floyd后,把目的城市与起始城市的4+4个飞机场都扫一遍,取最小值。

答案输出

保留1位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
int x[801],y[801];
int ti[501];
int n,s,tt,a,b;
double d[501][501];
void doit(int t1,int t2)
{
d[t1][t2]=sqrt((x[t1]-x[t2])*(x[t1]-x[t2])+(y[t1]-y[t2])*(y[t1]-y[t2]));
if (((t1-1)/4)==((t2-1)/4))
{
d[t1][t2]=d[t1][t2]*ti[(t1-1)/4+1];
}else
d[t1][t2]=d[t1][t2]*tt;
d[t2][t1]=d[t1][t2];
return;
}
int find(int t1,int t2,int t3)//找直角三角形斜边
{
if ((d[t1][t2]>d[t2][t3])&&(d[t1][t2]>d[t3][t1])) return t3;
if ((d[t2][t3]>d[t1][t2])&&(d[t2][t3]>d[t3][t1])) return t1;
if ((d[t3][t1]>d[t2][t3])&&(d[t3][t1]>d[t1][t2])) return t2;
}
void doit2(int t1,int t2,int t3)//求第四个点的坐标(数学方法)
{
doit(t1,t2);
doit(t2,t3);
doit(t3,t1);
int haha=find(t1,t2,t3);
if (haha==t1)
{
x[t3+1]=x[t3]+x[t2]-x[t1];
y[t3+1]=y[t3]+y[t2]-y[t1];
}
if (haha==t2)
{
x[t3+1]=x[t3]+x[t1]-x[t2];
y[t3+1]=y[t3]+y[t1]-y[t2];
}
if (haha==t3)
{
x[t3+1]=x[t1]+x[t2]-x[t3];
y[t3+1]=y[t1]+y[t2]-y[t3];
}
}
int main()
{
scanf("%d",&n);
for (;n>0;n--)
{
scanf("%d %d %d %d",&s,&tt,&a,&b);
//S城市数,t飞机单价,A,B序号
int i,j,k;
for (i=1;i<=401;i++)
for (j=1;j<=401;j++)
d[i][j]=100000000;
for (i=1;i<=s;i++)
{
scanf("%d %d %d %d %d %d %d",
&x[4*i-3],&y[4*i-3],&x[4*i-2],
&y[4*i-2],&x[4*i-1],&y[4*i-1],
&ti[i]);
doit2(4*i-3,4*i-2,4*i-1);
}
for (i=1;i<=4*s;i++)
for (j=1;j<=4*s;j++)
doit(i,j);
for (k=1;k<=4*s;k++)
for (i=1;i<=4*s;i++)
for (j=1;j<=4*s;j++)
if (d[k][j]+d[i][k]<d[i][j])
{
d[i][j]=d[k][j]+d[i][k];
}
double ans=200000000.0;
for (i=4*a-3;i<=4*a;i++)
for (j=4*b-3;j<=4*b;j++)
if (d[i][j]<ans) ans=d[i][j];
printf("%.1lf\n",ans);
}
return 0;
}