2026 云斗学院软件能力认证第一轮（YDSP - Senior）逐题题解

判断题统一约定：A 表示正确，B 表示错误。

程序原文请配合题面中的高分辨率截图阅读；下文只引用必要的短小标识符，不重复抄录整段 C++ 程序。

答案总表

扁平题号	原卷位置	答案	分值
1～5	1.1～1.5	B、C、A、A、B	每题 2 分
6～10	1.6～1.10	A、A、C、D、C
11～15	1.11～1.15	D、B、A、C、D
16～20	2.1.1(1～3)、2.1.2(4～5)	B、A、B、C、A	1.5、1.5、2、3、4 分
21～26	2.2.1(1～3)、2.2.2(4～6)	B、A、B、A、C、D	1.5、1.5、2、2、3、4 分
27～32	2.3.1(1～3)、2.3.2(4～6)	A、B、A、B、C、B
33～37	3.1 Blank 1～5	D、B、C、B、A	每题 3 分
38～42	3.2 Blank 1～5	D、A、C、A、D

第一部分：选择题

第 1 题

答案：B

原卷映射：1.1 第 1 题。

推导：最小生成树要求从连通带权无向图中选出连接全部顶点且总边权最小的树。Prim 算法从一个顶点出发，每次加入连接当前集合与外部顶点的最小边，正是最小生成树算法。KMP 用于字符串匹配，Floyd 用于全源最短路，Tarjan 通常用于强连通分量、割点或桥，因此选 B。

第 2 题

答案：C

原卷映射：1.2 第 2 题。

推导：基数为 8 的最低位优先基数排序，第一轮只看各数除以 8 的余数，并保持同一桶内原顺序。五个数的余数依次为 $7,7,4,3,0$，按桶号 $0,3,4,7$ 收集得到 80, 27, 36, 39, 7。余数同为 7 的 39 和 7 仍按原顺序出现，所以选 C。

第 3 题

答案：A

原卷映射：1.3 第 3 题。

推导：C++ 运算符优先级中，乘法高于加法，加法又高于移位；两个 << 同级并按从左到右结合。因此原式等价于 $(5\ll(4+3\times2))\ll1$。依次把两个中缀子表达式转为后缀，得到 5 4 3 2 * + << 1 <<，即 A。

第 4 题

答案：A

原卷映射：1.4 第 4 题。

推导：命令行参数必须紧跟可执行文件，所以参数 D 写作 ./A D；标准输入重定向使用 < B，标准输出重定向使用 > C。组合后为 ./A D < B > C，选 A。

第 5 题

答案：B

原卷映射：1.5 第 5 题。

推导：以 100 为中心、半径为 70 的回文串覆盖 $[30,170]$。中心 80 关于 100 的镜像中心是 120，两者离中心 100 的距离都是 20。回文半径的镜像性质给出

$$r_{120}\ge \min(r_{80},r_{100}-20)=\min(60,50)=50.$$

中央回文右边界只保证镜像回文延伸到 170，即相对中心 120 的半径 50；题目没有条件保证继续延伸，因此能确定的下界是 50，选 B。

第 6 题

答案：A

原卷映射：1.6 第 6 题。

推导：设一个周期开始时朝向角为 $0^\circ$。四次前进方向依次是 $0^\circ,60^\circ,120^\circ,60^\circ$，四个单位向量之和为

$$1+e^{i60^\circ}+e^{i120^\circ}+e^{i60^\circ}=3e^{i60^\circ}.$$

一个周期结束后的净转角为 $60+60-60-30=30^\circ$。因此连续周期位移构成公比为 $e^{i30^\circ}$ 的等比向量和，经过 12 个周期后十二个方向绕满一周，位移和为 0。

还需排除更早在周期中途回到原点。经过 $k$ 个完整周期的位移大小为 $3|\sin(15k^\circ)|/\sin15^\circ$；当 $1\le k\le11$ 时至少为 3，而一个周期内前三步的部分位移大小至多为 2，不能抵消。故第一次回到原点恰在第 12 个周期末，共走 $12\times4=48$ 厘米，选 A。

第 7 题

答案：A

原卷映射：1.7 第 7 题。

推导：利用恒等式 $a\oplus b=a+b-2(a\mathbin{\&}b)$，且 $a\mathbin{\&}b\le b$，可得

$$a\oplus b\ge a-b.$$

又因为 $a-b$ 是 $q=\gcd(a,b)$ 的正倍数，所以 $a-b\ge q$，从而 $p=a\oplus b\ge q$。等号确实可能出现，例如 $a=6,b=4$ 时，$a\oplus b=2$ 且 $\gcd(a,b)=2$，故选 A。

第 8 题

答案：C

原卷映射：1.8 第 8 题。

推导：把每个子集 $S$ 看成一个图结点，操作 $S\to S\oplus\{x\}$ 是一条权为 $w(S,x)$ 的边。由于切换同一个元素可以来回，状态转移图有环，不能简单按子集大小做无环动态规划；又没有给出允许贪心的结构。

递推式要求的是从当前集合走到空集的最短路，所有边权非负，正好满足 Dijkstra 算法的使用条件。Floyd 需要处理全部状态对，状态数又有 $2^n$，明显没有必要。因此选 C。

第 9 题

答案：D

原卷映射：1.9 第 9 题。

推导：连通二分图的二染色在固定结点 1 所在一侧后唯一，所以 A 正确。欧拉回路要求每个结点度数均为正偶数；若某一部只有一个结点，另一部每个结点在简单图中只能与它相连，度数只能为 1，矛盾，所以 B 正确。

边数 $m$ 等于任意一部所有结点度数之和，而这些度数全为偶数，因此 $m$ 为偶数，C 正确。结点数却不必为偶数：左部三个结点度数为 $4,2,2$，右部四个结点度数都为 2 的连通简单二分图共有 7 个结点且有欧拉回路。故错误说法是 D。

第 10 题

答案：C

原卷映射：1.10 第 10 题。

推导：$b_i=1$ 恰好表示 $a_i$ 与 $a_{i+1}$ 之间出现颜色段边界。因此区间 $[l,r]$ 的颜色段数为

$$1+\sum_{i=l}^{r-1}b_i.$$

所以求 $a[100,\ldots,200]$ 的颜色段数确实需要计算 $b$ 在 $[100,199]$ 上的和，再加 1。选项 C 的措辞是“需要计算该和”，并没有声称该和本身就是最终段数，这是本题容易误读之处。

区间赋值时可以反复找到区间内现存的 1 并做单点清零；每次赋值最多新产生两个边界，总修改量可摊还，不强制需要懒标记，A 错。树状数组也支持点改、区间和与前缀定位，不增加渐进复杂度，B 错。线段树可以直接下行寻找下一个 1，复杂度为 $O(\log n)$，不是必须 $\Theta(\log^2n)$，D 错。

第 11 题

答案：D

原卷映射：1.11 第 11 题。

推导：s.upper_bound(i) 返回第一个严格大于 $i$ 的颜色段左端点。当前颜色段就在这个左端点的前一位结束，因此右端点为 *s.upper_bound(i)-1，选 D。

实现时必须在集合中额外放入哨兵 $n+1$。否则当 $i$ 位于最后一个颜色段时，upper_bound(i) 会等于 s.end()，解引用将产生未定义行为。A、C 得到的是当前颜色段左端点；B 在 $i$ 恰好为段首时会取到当前段首再减 1，也不正确。

第 12 题

答案：B

原卷映射：1.12 第 12 题。

推导：Alice 的一次区间赋值可能删除很多个边界，所以单次最坏复杂度不止 $O(\log n)$，A 错。但每个被删除的边界都必须先在初始序列中存在，或由此前某次赋值在两个端点处新建；一次赋值最多新建两个边界。

总操作数为 $O(n)$ 时，被插入和删除的边界总数也是 $O(n)$。每次在线段树中定位或点改花 $O(\log n)$，故总复杂度按摊还分析为 $O(n\log n)$，B 正确。Bob 的方法最好只需常数次集合定位，约为 $O(\log n)$，不是 $O(n)$；随机输入正是珂朵莉树常见的均摊良好情形，不能据此断言总复杂度必为 $O(n^2)$。

第 13 题

答案：A

原卷映射：1.13 第 13 题。

推导：条件 $p^4=\mathrm{id}$ 表示排列中每个循环的长度都必须整除 4，因此只允许长度 1、2、4。把 6 拆成这些循环长度，可能的循环型及数量为

$$\begin{aligned} 1^6 &:1,\\ 2\,1^4 &: \frac{6!}{2\cdot4!}=15,\\ 2^2 1^2 &: \frac{6!}{2^2\cdot2!\cdot2!}=45,\\ 2^3 &: \frac{6!}{2^3\cdot3!}=15,\\ 4\,1^2 &: \frac{6!}{4\cdot2!}=90,\\ 4\,2 &: \frac{6!}{4\cdot2}=90. \end{aligned}$$

合计 $1+15+45+15+90+90=256$，选 A。

第 14 题

答案：C

原卷映射：1.14 第 14 题。

推导：$1001=7\times11\times13$，三个模数两两互质，可以分别计数后用中国剩余定理相乘。

模 7 时 $909\equiv-1$，方程 $x^3\equiv-1$ 有 3 个解；模 11 时 $909\equiv7$，因为 $\gcd(3,10)=1$，立方映射在非零剩余类上是双射，所以有 1 个解；模 13 时 $909\equiv-1$，在阶为 12 的乘法群中有 3 个立方根。总解数为 $3\times1\times3=9$，选 C。

第 15 题

答案：D

原卷映射：1.15 第 15 题。

推导：由前序和中序遍历重建树：根为 $C$；左子树根为 1，1 的左孩子为 $D$；$D$ 的左子树为 $8$（其左孩子为 4），右子树为 $5$（左孩子 3，右孩子 $A$，而 $A$ 的左右孩子为 2、7）；$C$ 的右子树为 6，其右孩子为 $B$。

$\operatorname{LCA}(1,11)=11$ 要求编号 11 所在的字母结点是 1 的祖先，四个字母中只有 $C$ 满足，所以 $C=11$。随后 $\operatorname{LCA}(2,10)=C$，剩余字母中只有把 $B$ 置为 10 才会使 2 与 10 分居根 $C$ 两侧，因此 $B=10$。

此时 $A,D$ 分别取 9、12。结点 4 在 $D$ 的左子树，$A$ 在 $D$ 的右子树，故 $\operatorname{LCA}(4,A)=D$。要满足 $\operatorname{LCA}(4,9)=12$，只能有 $A=9,D=12$。最大数字 12 位于 $D$，选 D。

第二部分：阅读程序

第一组程序概览（对应第 16～20 题）


程序先统计字符串中所有相邻字符转移的次数，p[x][y] 表示字符 $x$ 后面紧接字符 $y$ 的次数。随后以 $s$ 的最后一个字符为当前字符，重复 $m$ 次：扫描 26 个候选后继，选出现次数最多者输出，并把它作为下一轮当前字符。

mx=0,y=0 且比较使用严格大于号，所以并列最大值保留字典序最小者；如果整行转移次数都为 0，也输出 a。预处理耗时 $O(n)$，生成答案耗时 $O(26m)$，除输入字符串外只使用 $26\times26$ 的常数表。

第 16 题

答案：B（错误）

原卷映射：2.1.1 判断题第 1 题。

推导：输出语句位于循环 for(int i=1; i<=m; i++) 中，每轮恰输出一个字符，所以输出长度恒为 $m$。$n$ 只影响转移计数表的内容，不决定输出长度。因此命题错误，选 B。

第 17 题

答案：A（正确）

原卷映射：2.1.1 判断题第 2 题。

推导：若某行存在正转移次数，把初值从 0 改为 $-1$ 后，后续扫描仍会选到相同的最大正值及最小下标。若该行所有次数都是 0，原程序因 y=0 输出 a；修改后在 $j=0$ 时有 $0>-1$，仍把 y 设为 0，之后严格大于不再成立，也输出 a。两种情况结果都不变，命题正确。

第 18 题

答案：B（错误）

原卷映射：2.1.1 判断题第 3 题。

推导：严格 > 在并列时保留先扫描到的较小字母，改成 >= 会不断用后扫描到的字母覆盖，变成选字典序较大者。极端情况下整行次数全为 0，原程序输出 a，修改后甚至会一路更新到 z。输出可能改变，故命题错误。

第 19 题

答案：C

原卷映射：2.1.2 选择题第 4 题。

推导：第一次进入生成循环时，x=s[n]-'a'，所以只查看 $s$ 最后一个字符对应的转移表行。该行统计它在所有有后继的出现位置之后分别接了什么字符；扫描使用严格大于号，因此频次并列时选字典序较小者。与选项 C 完全一致。

第 20 题

答案：A

原卷映射：2.1.2 选择题第 5 题。

推导：对 daedacbace 统计有用转移：d->a 两次，a->c 两次、a->e 一次，e->d 一次，c->b 与 c->e 各一次，b->a 一次。末字符是 e，于是生成链为

$$e\to d\to a\to c\to b\to a\to c\to b.$$

输出的是每条箭头到达的字符，共 7 个，即 dacbacb，选 A。

第二组程序概览（对应第 21～26 题）


每条输入三元组 $(u,v,x)$ 可看作一个异或约束 $val_u\oplus val_v=x$。并查集的 w[u] 维护 $u$ 到父亲的异或值；Find 路径压缩时把它累积为 $u$ 到根的异或值，所以同一集合中两点应满足的异或值是 w[u]^w[v]。

若新约束与当前集合矛盾，程序用 stk 撤销当前批次内的全部合并，把答案加 1，再把这条导致矛盾的约束作为新批次的第一条约束加入。因而 ans 表示按输入顺序贪心切分后得到的最少连续一致段数。栈中每个合并结点至多被压入一次、在一次清空中弹出一次，清空总工作量可按合并次数摊还。

第 21 题

答案：B（错误）

原卷映射：2.2.1 判断题第 1 题。

推导：原 do-while 只撤销栈中本批次实际发生的合并。所有批次合计的压栈与弹栈次数不超过输入边数的常数倍。若每次矛盾都调用 init()，无论本批次有多少合并都要扫描 $n$ 个结点；矛盾可出现 $O(m)$ 次，复杂度可能增加到 $O(nm)$。两者不同，命题错误。

第 22 题

答案：A（正确）

原卷映射：2.2.1 判断题第 2 题。

推导：ans 初值为 1，只有遇到矛盾才加 1。第一条约束不可能与空并查集矛盾，因此至多后面的 $m-1$ 条都触发加一，最终不超过 $m$。取同一对点并让约束值交替出现，第一条建立关系，此后每条都与当前批次冲突，可达到 $ans=m$，所以命题正确。

第 23 题

答案：B（错误）

原卷映射：2.2.1 判断题第 3 题。

推导：只有 fa[u]==fa[v] 时才可能进入撤销，而题目保证 $u\ne v$。两点能处在同一集合，当前批次至少发生过一次合并，因此 top>=1。循环先处理 stk[top]，再执行 --top；当它减到 0 时条件为假并立刻结束，不会继续减成负数。因此命题错误。

第 24 题

答案：A

原卷映射：2.2.2 选择题第 4 题。

推导：按题目假设，每次 Find 均摊 $O(1)$。每条约束只做常数次查找和比较；每次成功合并压栈一次，而每个栈项也只会在某次清空中弹出一次。总时间为 $O(n+m)$，当 $n,m$ 同阶时就是 $O(n)$，选 A。

第 25 题

答案：C

原卷映射：2.2.2 选择题第 5 题。

推导：前三条约束 1 xor 2=1、2 xor 3=1、3 xor 4=1 一致，并推出 4 xor 1=1。第四条要求 4 xor 1=0，产生第一次矛盾，ans 变为 2；清空后第四条成为新批次首条。

第五条又要求 4 xor 1=1，与当前批次的 4 xor 1=0 矛盾，ans 变为 3。因此输出 3，选 C。

第 26 题

答案：D

原卷映射：2.2.2 选择题第 6 题。

推导：输出 1 等价于四条约束整体一致。三个点之间有 3 种无向边；每次输入还可选择两个方向，所以固定无向边序列后有 $2^4$ 种方向安排。

若四次都使用同一种无向边，共 3 个序列，约束秩为 1，异或值有 2 种一致赋法。其余 $3^4-3=78$ 个无向边序列至少使用两种边；在三个点上任意两种不同边都连通全部点，约束秩为 2，所以有 $2^2=4$ 种一致赋法。总数为

$$2^4\bigl(3\times2+78\times4\bigr)=5088.$$

故选 D。

第三组程序概览（对应第 27～32 题）


bd 是模式串 $s$ 的 KMP 失配数组，to[k][c] 表示当前已匹配 $s$ 的前缀长度为 $k$ 时追加字符 $c$ 后的新状态。tag 记录此前是否曾到达完整匹配状态 $n$，一旦变为 1 就不会恢复。

f[x][y][k][tag] 统计两份 $t$ 中分别以位置 $x,y$ 结尾、内容相同的一对子序列，并记录其公共字符串的 KMP 状态。只有 t[x]==t[y] 时才能同时追加；sum 是对 $x,y$ 的二维前缀和，使所有前驱位置的总数能在 $O(1)$ 时间取得。最终把 tag=1 的状态求和，也就是统计公共字符串中包含 $s$ 作为连续子串的有序子序列对。

状态循环共 $O(m^2n)$，KMP 自动机预处理为 $O(26n)$，空间为 $O(m^2n)$。

第 27 题

答案：A（正确）

原卷映射：2.3.1 判断题第 1 题。

推导：逐位计算 aabaaab 的最长真前后缀长度：第 1 位为 0；aa 为 1；aab 为 0；aaba 为 1；aabaa 为 2；aabaaa 失配后回退并得到 2；完整串以 aab 为前后缀，得到 3。因此序列正是 {0,1,0,1,2,2,3}，命题正确。

第 28 题

答案：B（错误）

原卷映射：2.3.1 判断题第 2 题。

推导：二维前缀和使用包含排除，最后一步执行减法。在 C++ 中负数取模仍可能保留负号；即使真实计数非负，前面的加法已分别取模，当前代表元也可能小于被减的代表元，从而得到负值。ans 汇总这些代表元后同样可能为负，所以第 61 行把它加回模数是必要的。命题错误。

第 29 题

答案：A（正确）

原卷映射：2.3.1 判断题第 3 题。

推导：只有公共子序列的字符串中连续出现了 $s$，tag 才会变成 1。若 $s$ 连作为普通子序列都不是 $t$ 的子序列，那么任意从 $t$ 选出的子序列更不可能包含 $s$；所有 tag=1 状态均为 0，输出必为 0。命题正确。

第 30 题

答案：B

原卷映射：2.3.2 选择题第 4 题。

推导：原循环在 $x=0$ 时必须停止回退，再单独判断首字符是否匹配。删除 x>0 后，若 $x=0$ 且当前字符不等于 $s_1$，循环体会反复执行 x=bd[0]=0，状态永远不变，形成死循环。因此可能超出时间限制，选 B。

第 31 题

答案：C

原卷映射：2.3.2 选择题第 5 题。

推导：在 aaacspaa 中，c,s,p 只在第 4、5、6 位各出现一次。要让所选公共字符串包含 csp，两份子序列都必须选这三位；其余只能在前面 3 个 a 和后面 2 个 a 中选择。

两份子序列内容相同，要求前部选取相同数量的 a，后部也选相同数量。利用范德蒙德恒等式，答案为

$$\left(\sum_{i=0}^{3}\binom3i^2\right) \left(\sum_{j=0}^{2}\binom2j^2\right) =\binom63\binom42=20\times6=120.$$

故选 C。

第 32 题

答案：B

原卷映射：2.3.2 选择题第 6 题。

推导：两份子序列内容相同首先要求长度相同。长度为 $k$ 时，每份最多有 $\binom5k$ 种位置集合，因此相等的有序对数不超过 $\binom5k^2$。把 $t$ 的 5 个字符全部设为同一字符时，同长度的任意两份子序列都相等，达到这个上界。

再取长度为 1 的 $s$ 为该字符，所有非空公共字符串都包含 $s$，而空串不计入。最大输出为

$$\sum_{k=1}^{5}\binom5k^2=\binom{10}{5}-1=252-1=251.$$

故选 B。

第三部分：完善程序

组合问题概览（对应第 33～37 题）


长度为 $m$ 的序列中，数字 $i$ 恰好出现 $x_i$ 次，本质上是含重复元素的排列计数，答案为

$$\frac{m!}{\prod_{i=1}^{n}x_i!}\pmod {998244353}.$$

程序预处理阶乘 fac 和逆阶乘 ifac，再按 $i=1,2,\ldots,n$ 逐类加入元素。若加入当前 $x_i$ 个元素后前缀总数为 sum，就从 sum 个位置中选择 $x_i$ 个给新元素，乘上 $\binom{sum}{x_i}$。各步乘积会望远镜化为上述多重集排列公式。预处理时间、空间均为 $O(N)$，读入后的组合累计为 $O(n)$。

第 33 题

答案：D

原卷映射：3.1 Blank 1。

推导：inv(x) 要求模质数 mod 下的乘法逆元。由费马小定理，对不被 mod 整除的 $x$ 有 $x^{mod-1}\equiv1\pmod {mod}$，所以 $x^{-1}\equiv x^{mod-2}$。fpow 的默认指数应为 mod-2，选 D。若填 0、mod 或 mod-1，返回的分别是 1、$x$、1，都不是一般逆元。

第 34 题

答案：B

原卷映射：3.1 Blank 2。

推导：逆阶乘满足

$$(i!)^{-1}=((i+1)!)^{-1}\cdot(i+1).$$

已知 ifac[i+1] 后，应执行 ifac[i]=ifac[i+1]*(i+1)%mod，选 B。这里乘的是 $i+1$ 本身，不是它的逆元；若乘 $i$，也会产生一位偏移。

第 35 题

答案：C

原卷映射：3.1 Blank 3。

推导：组合数公式为

$$\binom{x}{y}=\frac{x!}{y!(x-y)!}.$$

在模质数意义下用逆阶乘代替除法，即 fac[x]*ifac[y]%mod*ifac[x-y]%mod，选 C。函数已在 $x<y$ 时提前返回 0，合法下标下不需要额外边界处理。

第 36 题

答案：B

原卷映射：3.1 Blank 4。

推导：后续每读入一类元素都把一个组合数乘入 ans，因此 ans 是乘法累积量，单位元必须为 1。初始化为 0 会让答案永远为 0；fac[n]、ifac[n] 与当前已放置的元素总数无关。故选 B。

第 37 题

答案：A

原卷映射：3.1 Blank 5。

推导：代码先执行 sum+=x[i]，此时 sum 已经是加入当前类别后的前缀总数。应在这 sum 个位置中选出 $x_i$ 个位置放当前数字，所以乘上 C(sum,x[i])，即选 A。

各步乘积为

$$\prod_i\binom{x_1+\cdots+x_i}{x_i} =\prod_i\frac{(x_1+\cdots+x_i)!}{x_i!(x_1+\cdots+x_{i-1})!} =\frac{m!}{\prod_i x_i!},$$

正好是目标答案。选项 C 又加了一次 $x_i$，使用了错误的总位置数；加法选项也不能表示各类位置选择的乘法原理。

边权差最短路概览（对应第 38～42 题）


把原图的每条边变成辅助图中的一个结点。若两条原边在某个原顶点相接，路径就能从一条边转到另一条边，代价是两条边权之差的绝对值。起点 1 所有邻边与超级源点 $m+1$ 以 0 权相连，终点 $n$ 所有邻边与超级汇点 $m+2$ 以 0 权相连。

若在一个原顶点处把所有邻边两两连边，会产生 $O(\deg^2)$ 条辅助边。程序按边权排序后只连接相邻项；从权值 $a$ 走到权值 $b$ 时，沿排序链的各段差值会恰好望远镜为 $|a-b|$，既不改变最短距离，又把辅助边数降为 $O(m)$。随后在非负边权辅助图上运行 Dijkstra。

对所有邻接表排序总耗时 $O(m\log m)$，辅助边数和结点数均为 $O(m)$，Dijkstra 也是 $O(m\log m)$；空间为 $O(n+m)$。

第 38 题

答案：D

原卷映射：3.2 Blank 1。

推导：同一个 node::operator< 同时服务于普通 sort 和 priority_queue。Dijkstra 需要优先队列把较小的 dis 放在堆顶，因此比较应写成 dis>_.dis，把默认大根堆反转为小根堆。

这一写法也会让 sort(e[i]) 按 dis 从大到小排列，仍然满足只连接相邻边权的要求。若填 dis<_.dis，排序虽为升序，但优先队列会先弹出最大距离，破坏当前 vis 写法下的 Dijkstra。故选 D。

第 39 题

答案：A

原卷映射：3.2 Blank 2。

推导：上一空使 e[i] 按边权 dis 从大到小排列，所以相邻项满足 e[i][j].dis>=e[i][j+1].dis。两条辅助结点之间的边权应为两原边权的绝对差，此时可直接写成 e[i][j].dis-e[i][j+1].dis，选 A。选 B 会得到非正数，破坏 Dijkstra 的非负边权前提。

第 40 题

答案：C

原卷映射：3.2 Blank 3。

推导：辅助图中编号 $1\ldots m$ 对应原图边，m+1 是连接原起点 1 所有邻边的超级源点，m+2 是超级汇点。代码已令 dis[m+1]=0，所以优先队列最初必须压入 node(m+1,0)，选 C。

第 41 题

答案：A

原卷映射：3.2 Blank 4。

推导：同一辅助结点可能因多次松弛进入优先队列。第一次按最小距离弹出后置 vis[u]=1，以后再次弹出旧记录时应直接跳过，所以条件是 vis[u]==1，选 A。是否为无穷、编号是否超过 $n$ 或 $m$ 都不能判断这条队列记录是否已经完成最短路扩展。

第 42 题

答案：D

原卷映射：3.2 Blank 5。

推导：超级汇点编号为 $m+2$，所有与原终点 $n$ 相接的边结点都以 0 代价连接它。因此从超级源点 $m+1$ 到 $m+2$ 的最短距离，恰好是从原点 1 到原点 $n$ 的最小边权差费用。最终应输出 dis[m+2]，选 D。