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

题目描述

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。

用例输入

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;
}