2023 年 5 月青少年软编等考 C 语言八级真题解析

T1. 道路

题目链接：SOJ D1216

$N$ 个以 $1\sim N$ 标号的城市通过单向的道路相连，每条道路包含两个参数：道路的长度和需要为该路付的通行费（以金币的数目来表示）。

Bob 和 Alice 过去住在城市 $1$，在注意到 Alice 在他们过去喜欢玩的纸牌游戏中作弊后，Bob 和她分手了，并且决定搬到城市 $N$。他希望能够尽可能快的到那，但是他囊中羞涩。我们希望能够帮助 Bob 找到从 $1$ 到 $N$ 最短的路径，前提是他能够付的起通行费。

时间限制：1 s
内存限制：64 MB

• 输入
  第一行包含一个整数 $K$，$0\le K\le 10000$，代表 Bob 能够在他路上花费的最大的金币数。
  第二行包含整数 $N$，$2\le N\le 100$，指城市的数目。
  第三行包含整数 $R$，$1\le R\le 10000$，指路的数目。
  接下来的 $R$ 行，每行具体指定几个整数 $S,D,L$ 和 $T$ 来说明关于道路的一些情况，这些整数之间通过空格间隔：$S$ 是道路起始城市，$1\le S\le N$，$D$ 是道路终点城市，$1\le D\le N$，$L$ 是道路长度，$1\le L\le 100$，$T$ 是通行费（以金币数量形式度量），$0\le T\le 100$。注意不同的道路可能有相同的起点和终点。
• 输出
  输入结果应该只包括一行，即从城市 $1$ 到城市 $N$ 所需要的最小的路径长度（花费不能超过 $K$ 个金币）。如果这样的路径不存在，结果应该输出 $-1$。
• 样例输入

  5
  6
  7
  1 2 2 3
  2 4 3 3
  3 4 2 4
  1 3 4 1
  4 6 2 1
  3 5 2 0
  5 4 3 2
  

• 样例输出

  11
  

思路分析

此题考查图论最短路径问题，是一道较好的基础应用题。

在数据量较小的情况下（大约 $N\le 1000$），最短路径问题可以用 $\mathtt{BFS}$ 进行求解，更快速的方式是使用堆优化的 $\mathtt{Dijkstra}$ 算法。示例代码采用链式前向星存图，用堆（优先队列替代）优化的 $\mathtt{Dijkstra}$ 算法求解最短路，通过运算符重载来规定优先队列中成员的优先级。

此题涉及到代价和距离两个属性，应以距离为第一优先级参数，距离相同时，考虑代价为第二优先级参数。需要注意的是，优先队列默认为大根堆，可以通过重载小于号 < 实现小根堆，其中距离较长的元素的优先级高于距离较短者，代价较高的元素的优先级高于代价较低者（也可以通过给参与优先级比较的成员添加负号 - 来实现小根堆，免去运算符重载的麻烦）。

常规 $\mathtt{Dijkstra}$ 算法通过定义 $dist$ 数组存储从起点到每个点的最短路径长度，来限制只有更新了最短路径长度的顶点入队。此题应该限制代价不超过 $k$ 的元素入队，与最短路径更新与否无关，因为距离最短的路径的总代价并不一定支付得起。也正因如此，每个顶点可能被其它代价更小的路径再次访问，不能添加标记数组对顶点进行分类。

/** Name: T1.cpp* Problem: 道路* Author: Teacher Gao.* Date&Time: 2025/05/14 22:48*/#include <bits/stdc++.h>using namespace std;// 链式前向星的数据结构
int to[10005], wl[10005], wt[10005], nxt[10005];
int head[105], tot;void add_edge(int x, int y, int w1, int w2) {++tot;to[tot] = y, wl[tot] = w1, wt[tot] = w2;	// 存储边信息nxt[tot] = head[x], head[x] = tot;			// 头插法
}int k, n, m;// 用于优先队列的数据结构
struct node {int dis, cost, id;bool operator < (const node &a) const {		// 重载小于号if (dis != a.dis) return dis > a.dis;	// 第一优先级return cost > a.cost;					// 第二优先级}
};int dijkstra(int s) {priority_queue<node> Q;Q.push({0, 0, 1});while (Q.size()) {node x = Q.top(); Q.pop();if (x.id == n) {return x.dis;}for (int i = head[x.id]; i; i = nxt[i]) {if (x.cost + wt[i] <= k) {Q.push({x.dis + wl[i], x.cost + wt[i], to[i]});}}}return -1;
}int main()
{ios::sync_with_stdio(false);cin.tie(