題目描述

A國與B國是相鄰的兩個國家，每個國家都有很多城市。國家內(nèi)部有很多連接城市的公路，國家之間也有很多跨國公路，連接兩個國家的邊界城市。兩個國家一共有N個城市，編號從1到N，一共有M條公路，包括國內(nèi)公路與跨國公路。小明生活在A國的城市1（即編號為1的城市），想去B國的城市N游玩，由于小明辦理的是只能入境一次的簽證，所以從城市1到城市N的路徑中，只能通過一條跨國公路。每條公路都有一個距離，并且通過這條公路會有一個花費。請幫小明計算出從城市1到城市N的最短距離，在距離最短的前提下，再計算出最少花費。如果無法到達城市N，輸出-1。

輸入描述

• 第一行是一個整數(shù)N，表示兩個國家的城市數(shù)量
• 第二行是一個整數(shù)M，表示兩個國家的公路數(shù)量，包括國內(nèi)公路與跨國公路
• 第三行是一個長度為N的字符串，字符串第i個（從1開始計數(shù)）字符為A或B，表示城市i屬于A國或B國，其中第1個字符一定為A，第N個字符一定為B
• 接下來M行，每行包含4個整數(shù)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

可以找到一條最優(yōu)線路：城市1(A國) → 城市3(B國) → 城市4(B國) → 城市5(B國)。而且只通過一條跨國公路：城市1 → 城市3。

• 距離 = 200 + 170 + 170 = 540
• 花費 = 1 + 7 + 9 = 17

解題思路

我們可以使用 BFS （廣度優(yōu)先搜索）來解決這個問題。BFS 是處理最短路徑問題的有效方法，但因為該問題同時涉及到 最短距離 和 最小花費，并且約束條件是最多只能使用一次跨國公路，因此我們需要對狀態(tài)進行細致管理。

我們定義一個 狀態(tài)結(jié)構(gòu)體 (State) 來表示每個城市的狀態(tài)，包括當前城市編號、當前總距離、當前總花費以及是否已經(jīng)過跨國公路。為了保證同時考慮距離和花費，我們將每個城市分為兩種狀態(tài)：

• flag = 0 表示還沒有經(jīng)過跨國公路。
• flag = 1 表示已經(jīng)經(jīng)過一次跨國公路。

使用 隊列 (queue) 來模擬 BFS，對于每條公路（國內(nèi)或跨國），根據(jù)是否是跨國公路的條件進行更新：

• 對于 國內(nèi)公路，可以繼續(xù)前進。
• 對于 跨國公路，只能走一次，且必須確保不重復跨國。

最終，通過 BFS 搜索完成后，輸出到達城市N的最短距離和最小花費。

優(yōu)化點：使用優(yōu)先隊列

代碼

#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 {// 優(yōu)先按距離排，再按花費排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;  // 如果當前狀態(tài)不是最優(yōu)的，跳過}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) {// 國內(nèi)公路，繼續(xù)走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 });}}}}}// 輸出結(jié)果if (dist[n] == INT_MAX) {cout << -1 << endl;  // 如果無法到達城市N}else {cout << dist[n] << " " << cost[n] << endl;  // 輸出最短距離和最小花費}return 0;
}