A27922. 旅游规划有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。输入输入说明：输入数据的第 1 行给出 4 个正整数 n、m、s、d，其中 n（2 ≤ n ≤ 500）是城市的个数，顺便假设城市的编号为 0~(n-1)；m 是高速公路的条数…
填空题
困难
知识点
题目描述
旅游规划
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。
输入
输入说明：输入数据的第 1 行给出 4 个正整数 n、m、s、d，其中 n（2 ≤ n ≤ 500）是城市的个数，顺便假设城市的编号为 0~(n-1)；m 是高速公路的条数；s 是出发地的城市编号；d 是目的地的城市编号。随后的 m 行中，每行给出一条高速公路的信息，分别是：城市 1、城市 2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过 500。输入保证解的存在。
输出
在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。
样例输入
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20样例输出
3 40参考答案
#include <iostream>
#include <vector>
#include <queue>
#include <climits> // 引入INT_MAX
using namespace std;
typedef pair<int, int> pii; // pair表示(长度, 费用)
typedef pair<int, pii> piii; // pair表示(城市编号, (长度, 费用))
struct Edge {
int to, length, cost;
};
vector<Edge> graph[505]; // 邻接表表示的图
int n, m, s, d; // n表示城市数量，m表示高速公路数量，s表示出发地，d表示目的地
vector<int> dist, cost; // dist记录最短路径长度，cost记录对应路径的费用
void dijkstra(int start) {
priority_queue<piii, vector<piii>, greater<piii>> pq; // 最小堆优先队列
pq.push({start, {0, 0}}); // 初始点，长度为0，费用为0
dist[start] = 0;
cost[start] = 0;
while (!pq.empty()) {
int u = pq.top().first;
int len = pq.top().second.first;
int fee = pq.top().second.second;
pq.pop();
if (len > dist[u]) continue; // 如果当前路径不是最短路径，则跳过
for (const Edge &e : graph[u]) {
int v = e.to;
int newLen = len + e.length;
int newFee = fee + e.cost;
if (newLen < dist[v] || (newLen == dist[v] && newFee < cost[v])) {
// 如果发现更短的路径，或者路径长度相同但费用更低，则更新
dist[v] = newLen;
cost[v] = newFee;
pq.push({v, {newLen, newFee}});
}
}
}
}
int main() {
cin >> n >> m >> s >> d;
dist.assign(n, INT_MAX); // 初始化距离为最大值
cost.assign(n, INT_MAX); // 初始化费用为最大值
for (int i = 0; i < m; ++i) {
int u, v, length, costum;
cin >> u >> v >> length >> costum;
graph[u].push_back({v, length, costum});
graph[v].push_back({u, length, costum}); // 如果是无向图，则需要添加这行
}
dijkstra(s);
cout << dist[d] << " " << cost[d] << endl; // 输出最短路径的长度和费用
return 0;
}
上一题
下一题