【NOIP提高组】Car的旅行路线

💐The Begin💐点点关注，收藏不迷路💐

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

那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。

输入

第一行有四个正整数s，t，A，B。S(0 接下来有S行，其中第I行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分别是第I个城市中任意三个机场的坐标，T I为第I个城市高速铁路单位里程的价格。

输出

输出最小费用(结果保留两位小数)

样例输入

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

样例输出

47.5

C++实现：

#include <iostream>
#include <iomanip>
#include <cmath>
#include <limits>// 计算两点之间的欧氏距离的平方
double distanceSquared(double x1, double y1, double x2, double y2) {return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}// 计算两点之间的欧氏距离
double distance(double x1, double y1, double x2, double y2) {return std::sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}int main() {long long TTT;std::cin >> TTT;// 读取测试用例的数量while (TTT--) {// 初始化各种变量和数组long long s;double t;long long A, B;double ans = std::numeric_limits<double>::max();// 读取输入的参数 s、t、A、Bstd::cin >> s >> t >> A >> B;double x[410];double y[410];double T[110];double dis[410][410];// 初始化距离数组为最大值for (int i = 0; i < 410; ++i) {for (int j = 0; j < 410; ++j) {dis[i][j] = std::numeric_limits<double>::max();}}// 输入四个点的坐标和时间，并计算第四个点的坐标for (int i = 1; i <= s; ++i) {std::cin >> x[(i - 1) * 4 + 1] >> y[(i - 1) * 4 + 1] >> x[(i - 1) * 4 + 2] >> y[(i - 1) * 4 + 2] >> x[(i - 1) * 4 + 3] >> y[(i - 1) * 4 + 3] >> T[i];double dab = distanceSquared(x[(i - 1) * 4 + 1], y[(i - 1) * 4 + 1], x[(i - 1) * 4 + 2], y[(i - 1) * 4 + 2]);double dac = distanceSquared(x[(i - 1) * 4 + 1], y[(i - 1) * 4 + 1], x[(i - 1) * 4 + 3], y[(i - 1) * 4 + 3]);double dbc = distanceSquared(x[(i - 1) * 4 + 2], y[(i - 1) * 4 + 2], x[(i - 1) * 4 + 3], y[(i - 1) * 4 + 3]);if (dab + dac == dbc) {x[i * 4] = x[(i - 1) * 4 + 2] + x[(i - 1) * 4 + 3] - x[(i - 1) * 4 + 1];y[i * 4] = y[(i - 1) * 4 + 2] + y[(i - 1) * 4 + 3] - y[(i - 1) * 4 + 1];} else if (dab + dbc == dac) {x[i * 4] = x[(i - 1) * 4 + 1] + x[(i - 1) * 4 + 3] - x[(i - 1) * 4 + 2];y[i * 4] = y[(i - 1) * 4 + 1] + y[(i - 1) * 4 + 3] - y[(i - 1) * 4 + 2];} else if (dbc + dac == dab) {x[i * 4] = x[(i - 1) * 4 + 2] + x[(i - 1) * 4 + 1] - x[(i - 1) * 4 + 3];y[i * 4] = y[(i - 1) * 4 + 2] + y[(i - 1) * 4 + 1] - y[(i - 1) * 4 + 3];}}// 计算两点之间的距离，并填充距离数组for (int i = 1; i <= s * 4; ++i) {for (int j = 1; j <= s * 4; ++j) {if (i!= j) {if ((i - 1) / 4!= (j - 1) / 4) {dis[i][j] = t * distance(x[i], y[i], x[j], y[j]);} else {dis[i][j] = T[(i - 1) / 4 + 1] * distance(x[i], y[i], x[j], y[j]);}}}}// 使用 Floyd-Warshall 算法更新距离数组for (int k = 1; k <= s * 4; ++k) {for (int i = 1; i <= s * 4; ++i) {for (int j = 1; j <= s * 4; ++j) {dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);}}}// 计算从 A 到 B 的最短距离for (int i = 1; i <= 4; ++i) {for (int j = 1; j <= 4; ++j) {ans = std::min(ans, dis[(A - 1) * 4 + i][(B - 1) * 4 + j]);}}// 输出结果，保留一位小数std::cout << std::fixed << std::setprecision(1) << ans << std::endl;}return 0;
}

以下是对这段 C++代码的解析：

一、整体功能概述

这段代码用于解决一个与计算两点之间最短距离相关的问题。给定多个四边形，每个四边形由四个点组成，通过输入相关参数和点的坐标，计算从一个指定四边形的某一点到另一个指定四边形的某一点的最短距离。

二、函数解析

1. distanceSquared函数：

   • 计算两个点之间距离的平方。接受两个点的坐标作为参数，通过计算坐标之差的平方和来得到距离的平方值。

2. distance函数：

   • 计算两个点之间的欧氏距离。调用distanceSquared函数得到距离的平方，然后对其开方得到实际的距离值。

3. main函数：

   • 输入与初始化：

     • 首先从标准输入读取测试用例的数量TTT。
     • 在每次测试用例中，读取参数s（四边形的数量）、t（在不同四边形之间移动的速度相关参数）、A和B（分别表示起始和目标四边形的编号）。
     • 初始化变量ans为一个极大值，表示最短距离的初始值。
     • 初始化二维数组dis，用于存储所有点对之间的距离，初始值设为极大值。

   • 计算第四个点的坐标：

     • 通过循环输入每个四边形的四个点的坐标和对应的时间T[i]。
     • 对于每个四边形，根据已知的三个点坐标，通过判断三个边长的关系（利用距离的平方函数）来计算第四个点的坐标。

   • 填充距离数组：

     • 再次使用两层循环遍历所有可能的点对。
     • 如果两个点不在同一个四边形中，距离计算公式为t乘以两点之间的欧氏距离；如果在同一个四边形中，距离计算公式为对应四边形的时间参数T[(i - 1) / 4 + 1]乘以两点之间的欧氏距离，并将结果存入距离数组dis。

   • Floyd-Warshall 算法更新距离：

     • 使用三层循环实现 Floyd-Warshall 算法，对距离数组dis进行更新，确保得到任意两点之间的最短距离。

   • 计算最短距离：

     • 最后通过两层循环遍历起始四边形A和目标四边形B的四个顶点组合，找到从A的某一点到B的某一点的最短距离，更新ans。

   • 输出结果：

     • 将最短距离以保留一位小数的形式输出到标准输出。

三、时间复杂度和空间复杂度分析

1. 时间复杂度：

   • 输入部分的时间复杂度取决于输入的大小，假设输入的点数为n，输入操作的时间复杂度为$O(n)$。
   • 计算第四个点坐标的循环时间复杂度为$O(s)$，其中s是四边形的数量。
   • 填充距离数组的双重循环时间复杂度为$O(n^2)$，其中n是总点数（这里是s * 4）。
   • Floyd-Warshall 算法的时间复杂度为$O(n^3)$。
   • 计算最短距离的双重循环时间复杂度为$O(16)$（因为最多有 4 个顶点的起始四边形和目标四边形）。
   • 总体时间复杂度主要由 Floyd-Warshall 算法决定，为$O(n^3)$。

2. 空间复杂度：

   • 存储点坐标的数组x、y和时间参数数组T的空间复杂度为$O(n)$，其中n是总点数。
   • 存储距离的二维数组dis的空间复杂度为$O(n^2)$。
   • 总体空间复杂度为$O(n^2)$。

💐The End💐点点关注，收藏不迷路💐