题目描述

作为一家初创航空公司的总裁，您需要开发一个程序来计算客户在现有航线网络中可能获得的最大常旅客里程数。里程数按照"直线飞行距离"（即地球表面两点间的最短路径）计算。地球被视为完美球体，半径为4000英里。

输入格式：

• 第一行是整数n，表示数据集的数量。
• 每个数据集包含：
  • 标题行："X Y"，X是城市数量，Y是直飞航线数量。
  • 城市列表：每行格式为"C LA NS LO EW"，表示城市名称、纬度、纬度方向、经度、经度方向。
  • 航班列表：每行格式为"B C"，表示城市B和C之间有直飞航班（双向）。

输出格式：

• 对每个数据集，输出相距最远的两个城市（即最短路径最长的城市对），按字典序排列。

解题思路

1. 数据预处理：

   • 将每个城市的经纬度转换为弧度形式，统一处理方向（N/S/E/W）。
   • 特别注意经度的表示方式（如180E和180W是等效的），需调整到[-180°, 180°]范围内。

2. 构建图模型：

   • 使用邻接矩阵表示城市间的连接关系，初始化所有距离为无穷大。
   • 根据航班列表填充邻接矩阵，直接相连的城市之间的距离通过球面距离公式计算。

3. 计算最短路径：

   • 使用Floyd-Warshall算法计算所有城市对之间的最短路径。该算法通过动态规划逐步更新最短路径，适用于稠密图。

4. 查找最长最短路径：

   • 遍历所有城市对，找到最短路径中最长的那个。
   • 按字典序输出这两个城市。

解决代码

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

const double INF = 1e18;
const double PI = acos(-1.0);

struct City {
	string name;
	double lat_rad;
	double lon_rad;
};

double calculate_distance(const City& a, const City& b) {
	double lat_a = a.lat_rad;
	double lon_a = a.lon_rad;
	double lat_b = b.lat_rad;
	double lon_b = b.lon_rad;
	
	double delta_lon = fabs(lon_a - lon_b);
	if (delta_lon > PI) {
		delta_lon = 2 * PI - delta_lon;
	}
	
	double cos_d = sin(lat_a) * sin(lat_b) + cos(lat_a) * cos(lat_b) * cos(delta_lon);
	
	// 处理精度问题，确保acos的参数在有效范围内
	if (cos_d > 1.0) cos_d = 1.0;
	else if (cos_d < -1.0) cos_d = -1.0;
	
	return 4000.0 * acos(cos_d);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	cin >> n;
	
	while (n--) {
		int X, Y;
		cin >> X >> Y;
		
		vector<City> cities;
		map<string, int> name_to_idx;
		
		for (int i = 0; i < X; ++i) {
			string name, ns, ew;
			int la, lo;
			cin >> name >> la >> ns >> lo >> ew;
			
			// 处理纬度
			double lat_degree = la;
			if (ns == "S") lat_degree *= -1;
			double lat_rad = lat_degree * PI / 180.0;
			
			// 处理经度
			double lon_degree = lo;
			if (ew == "W") lon_degree *= -1;
			// 调整经度到[-180, 180)范围内
			lon_degree = fmod(lon_degree, 360.0);
			if (lon_degree >= 180.0) {
				lon_degree -= 360.0;
			} else if (lon_degree < -180.0) {
				lon_degree += 360.0;
			}
			double lon_rad = lon_degree * PI / 180.0;
			
			cities.push_back({name, lat_rad, lon_rad});
			name_to_idx[name] = i;
		}
		
		// 初始化邻接矩阵
		vector<vector<double>> adj(X, vector<double>(X, INF));
		for (int i = 0; i < X; ++i) {
			adj[i][i] = 0.0;
		}
		
		// 填充邻接矩阵中的直接连接
		for (int i = 0; i < Y; ++i) {
			string a, b;
			cin >> a >> b;
			int u = name_to_idx[a];
			int v = name_to_idx[b];
			double dist = calculate_distance(cities[u], cities[v]);
			adj[u][v] = dist;
			adj[v][u] = dist;
		}
		
		// Floyd-Warshall算法计算所有节点对的最短路径
		for (int k = 0; k < X; ++k) {
			for (int i = 0; i < X; ++i) {
				for (int j = 0; j < X; ++j) {
					if (adj[i][k] + adj[k][j] < adj[i][j]) {
						adj[i][j] = adj[i][k] + adj[k][j];
					}
				}
			}
		}
		
		// 查找最大的最短路径
		double max_dist = -1;
		string city_a, city_b;
		for (int i = 0; i < X; ++i) {
			for (int j = i + 1; j < X; ++j) {
				if (adj[i][j] > max_dist) {
					max_dist = adj[i][j];
					city_a = cities[i].name;
					city_b = cities[j].name;
				}
			}
		}
		
		// 按字典序输出
		if (city_a > city_b) {
			swap(city_a, city_b);
		}
		cout << city_a << " " << city_b << endl;
	}
	
	return 0;
}

代码解释

1. 数据预处理：

   • 读取城市数据，将经纬度转换为弧度，并处理方向（N/S/E/W）。
   • 调整经度到[-180°, 180°]范围。

2. 距离计算：

   • 使用球面距离公式计算两个城市间的大圆距离。

3. 图模型构建：

   • 初始化邻接矩阵，填充直接相连的城市间的距离。

4. 最短路径计算：

   • 使用Floyd-Warshall算法计算所有城市对之间的最短路径。

5. 查找最长路径：

   • 遍历所有城市对，找到最短路径中最长的那个，并按字典序输出。