机试题——到邻国目标城市的最短距离

题目描述

A国与B国是相邻的两个国家，每个国家都有很多城市。国家内部有很多连接城市的公路，国家之间也有很多跨国公路，连接两个国家的边界城市。两个国家一共有N个城市，编号从1到N，一共有M条公路，包括国内公路与跨国公路。小明生活在A国的城市1（即编号为1的城市），想去B国的城市N游玩，由于小明办理的是只能入境一次的签证，所以从城市1到城市N的路径中，只能通过一条跨国公路。每条公路都有一个距离，并且通过这条公路会有一个花费。请帮小明计算出从城市1到城市N的最短距离，在距离最短的前提下，再计算出最少花费。如果无法到达城市N，输出-1。

输入描述

• 第一行是一个整数N，表示两个国家的城市数量
• 第二行是一个整数M，表示两个国家的公路数量，包括国内公路与跨国公路
• 第三行是一个长度为N的字符串，字符串第i个（从1开始计数）字符为A或B，表示城市i属于A国或B国，其中第1个字符一定为A，第N个字符一定为B
• 接下来M行，每行包含4个整数U, V, W, C，表示编号为U的城市与编号为V的城市之间存在一条公路，长度是W，花费是C。每条公路是双向的。

输出描述

• 输出城市1到城市N的最短距离，并在距离最短的前提下，再输出最少花费。如果无法到达城市N，输出-1。

用例输入

5 5 
AABBB 
3 1 200 1 
2 3 150 3 
5 2 160 5 
4 3 170 7 
4 5 170 9

540 17

可以找到一条最优线路：城市1(A国) → 城市3(B国) → 城市4(B国) → 城市5(B国)。而且只通过一条跨国公路：城市1 → 城市3。

• 距离 = 200 + 170 + 170 = 540
• 花费 = 1 + 7 + 9 = 17

解题思路

我们可以使用 BFS （广度优先搜索）来解决这个问题。BFS 是处理最短路径问题的有效方法，但因为该问题同时涉及到 最短距离 和 最小花费，并且约束条件是最多只能使用一次跨国公路，因此我们需要对状态进行细致管理。

我们定义一个 状态结构体 (State) 来表示每个城市的状态，包括当前城市编号、当前总距离、当前总花费以及是否已经过跨国公路。为了保证同时考虑距离和花费，我们将每个城市分为两种状态：

• flag = 0 表示还没有经过跨国公路。
• flag = 1 表示已经经过一次跨国公路。

使用 队列 (queue) 来模拟 BFS，对于每条公路（国内或跨国），根据是否是跨国公路的条件进行更新：

• 对于 国内公路，可以继续前进。
• 对于 跨国公路，只能走一次，且必须确保不重复跨国。

最终，通过 BFS 搜索完成后，输出到达城市N的最短距离和最小花费。

优化点：使用优先队列

代码

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;struct Edge {int u, v, w, c;
};struct State {int dist, cost, node, flag;bool operator>(const State& other) const {// 优先按距离排，再按花费排if (dist == other.dist) {return cost > other.cost;}return dist > other.dist;}
};int main() {int n, m;cin >> n >> m;string countries;cin >> countries;vector<vector<Edge>> graph(n + 1);  // 图的邻接表// 读取公路信息for (int i = 0; i < m; i++) {int u, v, w, c;cin >> u >> v >> w >> c;graph[u].push_back({ u, v, w, c });graph[v].push_back({ v, u, w, c });}// 初始化距离和花费vector<int> dist(n + 1, INT_MAX);vector<int> cost(n + 1, INT_MAX);dist[1] = 0;cost[1] = 0;priority_queue<State, vector<State>, greater<State>> pq;pq.push({ 0, 0, 1, 0 });  // 从城市1开始，距离0，花费0，未跨国while (!pq.empty()) {State current = pq.top();pq.pop();int u = current.node;int current_dist = current.dist;int current_cost = current.cost;int current_flag = current.flag;if (current_dist > dist[u] || (current_dist == dist[u] && current_cost > cost[u])) {continue;  // 如果当前状态不是最优的，跳过}for (const Edge& edge : graph[u]) {int v = edge.v;int next_dist = current_dist + edge.w;int next_cost = current_cost + edge.c;bool isSameCountry = (countries[u - 1] == countries[v - 1]);if (isSameCountry) {// 国内公路，继续走if (next_dist < dist[v] || (next_dist == dist[v] && next_cost < cost[v])) {dist[v] = next_dist;cost[v] = next_cost;pq.push({ next_dist, next_cost, v, current_flag });}}else {// 跨国公路，只能走一次if (current_flag == 0) {if (next_dist < dist[v] || (next_dist == dist[v] && next_cost < cost[v])) {dist[v] = next_dist;cost[v] = next_cost;pq.push({ next_dist, next_cost, v, 1 });}}}}}// 输出结果if (dist[n] == INT_MAX) {cout << -1 << endl;  // 如果无法到达城市N}else {cout << dist[n] << " " << cost[n] << endl;  // 输出最短距离和最小花费}return 0;
}