网站开发工程师需要具备的综合素质,成都个人兼职做网站,php网站开发价格,国际军事新闻最新消息题目描述
A国与B国是相邻的两个国家#xff0c;每个国家都有很多城市。国家内部有很多连接城市的公路#xff0c;国家之间也有很多跨国公路#xff0c;连接两个国家的边界城市。两个国家一共有N个城市#xff0c;编号从1到N#xff0c;一共有M条公路#xff0c;包括国内…题目描述
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 9540 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;vectorvectorEdge 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 });}// 初始化距离和花费vectorint dist(n 1, INT_MAX);vectorint cost(n 1, INT_MAX);dist[1] 0;cost[1] 0;priority_queueState, vectorState, greaterState 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;
}
