洛谷P1027（P1027 Car的旅行路线）

题目描述

又到暑假了，住在城市 A 的 Car 想和朋友一起去城市旅游。
她知道每个城市都有 4 个飞机场，分别位于一个矩形的 4 个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第 i 个城市中高速铁路了的单位里程价格为 $T_i$，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为 t。
那么 Car 应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。
找出一条从城市 A 到 B 的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。

输入格式

第一行为一个正整数 n，表示有 n 组测试数据。
每组的第一行有 4 个正整数 s,t,A,B。
S 表示城市的个数，t 表示飞机单位里程的价格，A，B 分别为城市A，B 的序号。
接下来有 S 行，其中第 i 行均有 7 个正整数 $x_{i1},y_{i1},x_{i2},y_{i2},x_{i3},y_{i3},T_i$ ，这当中的 $(x_{i1},y_{i1}),(x_{i2},y_{i2})，(x_{i3},y_{i3})$分别是第 i 个城市中任意 3 个机场的坐标， $T_i$为第 i 个城市高速铁路单位里程的价格。

输出格式

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

解题思路

我们把每个城市看成4个点，简单的floyd就好了。
对于每一次测试，都可以共用三个数组，一个是用来记录各个点的坐标的数组，一个是记录点与点之间距离的数组，还有一个是记录城市四个点之间高速的里程费用，我看到一些人还要memset，但是如果相同位置两次测试都要用到，那么后一次测试就会覆盖，如果用不到，那也不会对后一次测试造成影响。

代码

#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
double map[401][401];
int point[401][2];
int T[101];
int n;
void get_point(int j) {int x1 = point[j][0];int y1 = point[j][1];int x2 = point[j + 1][0];int y2 = point[j + 1][1];int x3 = point[j + 2][0];int y3 = point[j + 2][1];int len12 = (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2);int len23 = (x2 - x3)*(x2 - x3) + (y2 - y3)*(y2 - y3);int len13 = (x1 - x3)*(x1 - x3) + (y1 - y3)*(y1 - y3);if (len12 == (len23 + len13)) {point[j + 3][0] = x1 + x2 - x3;point[j + 3][1] = y1 + y2 - y3;return;}if (len23 == (len12 + len13)) {point[j + 3][0] = x2 + x3 - x1;point[j + 3][1] = y2 + y3 - y1;return;}if (len13 == (len12 + len23)) {point[j + 3][0] = x1 + x3 - x2;point[j + 3][1] = y1 + y3 - y2;return;}
}
void init(int s,int t) {for (int j = 0;j < s;j++) {for (int k = 0;k < s;k++) {if (j < k) {map[k][j] = 0;}if (!(map[k][j])) {if (j != k) {double len = sqrt(pow(point[j][0] - point[k][0], 2) + pow(point[j][1] - point[k][1], 2));if ((j / 4) == (k / 4)) {len *= T[j / 4];}else {len *= t;}map[j][k] = len;}}else {map[j][k] = map[k][j];}}}
}
void floyd(int a, int b,int s) {for (int p = 0;p < s;p++) {for (int m = 0;m < s;m++) {for (int n = 0;n < s;n++) {map[m][n] = min(map[m][n], map[m][p] + map[p][n]);}}}double ans = map[4 * a][4 * b];for (int j = 0;j < 4;j++) {for (int k = 0;k < 4;k++) {ans = min(ans, map[4 * a + j][4 * b + k]);}}cout << std::fixed << std::setprecision(1) << ans << endl;
}
void test() {int s, t, a, b;cin >> s >> t >> a >> b;a--;b--;for (int j = 0;j < 4 * s;j += 4) {cin >> point[j][0] >> point[j][1] >> point[j + 1][0] >> point[j + 1][1] >> point[j + 2][0] >> point[j + 2][1] >> T[j/4];get_point(j);}init(4 * s, t);floyd(a, b, 4 * s);
}
int main() {cin >> n;while (n--) {test(n);}return 0;
}