青少年软件编程（C语言）等级考试试卷（八级）
1
旅游规划
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。
时间限制：1000
内存限制：65536
输入
输入说明：输入数据的第 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 <bits/stdc++.h>
using namespace std;
struct Edge { int to, dist, cost; };
int main() {
int n, m, s, d; cin >> n >> m >> s >> d;
vector<vector<Edge>> g(n);
for (int i = 0, a, b, c, f; i < m; ++i) {
cin >> a >> b >> c >> f;
g[a].push_back({b, c, f});
g[b].push_back({a, c, f});
}
vector<int> dist(n, INT_MAX), fee(n, INT_MAX);
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
dist[s] = 0, fee[s] = 0; pq.emplace(0, 0, s);
while (!pq.empty()) {
auto [d, f, u] = pq.top(); pq.pop();
if (d > dist[u] || (d == dist[u] && f > fee[u])) continue;
for (auto &[v, dd, ff] : g[u]) {
if (d + dd < dist[v] || (d + dd == dist[v] && f + ff < fee[v])) {
dist[v] = d + dd, fee[v] = f + ff;
pq.emplace(dist[v], fee[v], v);
}
}
}
cout << dist[d] << " " << fee[d];
}
2
取帽子
拼题er们觉得戴帽子会令自己看上去很帅，所以他们不管到哪里都会戴着帽子。有一天他们去到一家餐厅，服务员把他们的帽子收集了堆起来保管。当大家要离开的时候，发现帽子被像上图那样摞起来了。于是你的任务就是帮他们排好队，使得每个人都能按顺序顺
202503C语言八级