2024年信奥赛C++提高组csp-s初赛真题及答案解析（完善程序第2题）
2024年信奥赛C++提高组csp-s初赛真题及答案解析（完善程序第2题）
第 2 题
（次短路） 已知一个有 n个点 m条边的有向图 G**，并且给定图中的两个点 s 和 t，求次短路（长度严格大于最短路的最短路径）。如果不存在，输出一行 −1。如果存在，输出两行，第一行表示次短路的长度，第二行表示次短路的一个方案。
#include - ① 处应填（ ）
A.upd(pre[b], n+b, dis[b], q)
B.upd(a, n+b, d, q)
C.upd(pre[b], b, dis[b], q)
D.upd(a, b, d, q) - ② 处应填（ ）
A.make_pair(-d, b)
B.make_pair(d, b)
C.make_pair(b, d)
D.make_pair(-b, d) - ③ 处应填（ ）
A.0xff
B.0x1f
C.0x3f
D.0x7f - ④ 处应填（ ）
A.upd(a, n+b, dis[a]+c, q)
B.upd(n+a, n+b, dis2[a]+c, q)
C.upd(n+a, b, dis2[a]+c, q)
D.upd(a, b, dis[a]+c, q) - ⑤ 处应填（ ）
A.pre2[a%n]
B.pre[a%n]
C.pre2[a]
D.pre[a%n]+1
题解：
本题要求求解有向图中从起点 (s) 到终点 (t) 的严格次短路（长度严格大于最短路）。代码采用 Dijkstra 算法的变种，将每个节点拆分成两个点：原点（对应最短路）和次短点（对应次短路），分别用距离数组 dis[0..n-1] 和 dis[n..2n-1] 记录。通过优先队列同时更新最短路和次短路，并记录前驱以输出路径。
算法思路：
- 使用双倍点集，分别维护最短路和次短路。
- 在 Dijkstra 过程中，从队列取出点 (aa)，若 (aa < n) 则为原点，否则为次短点。
- 更新时，若成功更新最短路，则将原最短路转移为次短路候选；若失败，则尝试更新次短路。
- 最终若次短路存在（
dis2[t] != inf），则输出长度并递归输出路径。
填空解析：
- ①：当更新原点 (b) 的最短路时，需要将原有的最短路作为次短路候选，因此调用
upd(pre[b], n+b, dis[b], q)，选 A。 - ②：优先队列默认大顶堆，为实现小顶堆需存入负距离，因此为
make_pair(-d, b)，选 A。 - ③：距离数组初始化为极大值，inf = 522133279,（十六进制为
0x1f1f1f1f），，选 B。 - ④：当最短路更新失败时，当前距离可能成为次短路，因此尝试用该距离更新次短点，调用
upd(a, n+b, dis[a]+c, q)，选 A。 - ⑤：输出次短路路径时，对于次短点 (a)（(a ge n)），其前驱为
pre[a]，即pre2[a%n]，选 A。
专栏推荐：信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html
各种学习资料，助力大家一站式学习和提升！！！
#include1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
· 文末祝福 ·
#include
