2024年信奥赛C++提高组csp-s初赛真题及答案解析（完善程序第2题）
第 2 题
（次短路）已知一个有 n个点 m条边的有向图 G**，并且给定图中的两个点 s 和 t，求次短路（长度严格大于最短路的最短路径）。如果不存在，输出一行 −1。如果存在，输出两行，第一行表示次短路的长度，第二行表示次短路的一个方案。
#include<cstdio>#include<queue>#include<utility>#include<cstring>usingnamespacestd;constintmaxn=2e5+10,maxm=1e6+10,inf=522133279;intn,m,s,t;inthead[maxn],nxt[maxm],to[maxm],w[maxm],tot=1;intdis[maxn<<1],*dis2;intpre[maxn<<1],*pre2;boolvis[maxn<<1];voidadd(inta,intb,intc){++tot;nxt[tot]=head[a];to[tot]=b;w[tot]=c;head[a]=tot;}boolupd(inta,intb,intd,priority_queue<pair<int,int>>&q){if(d>=dis[b])returnfalse;if(b<n)___①___;q.push(___②___);dis[b]=d;pre[b]=a;returntrue;}voidsolve(){priority_queue<pair<int,int>>q;q.push(make_pair(0,s));memset(dis,___③___,sizeof(dis));memset(pre,-1,sizeof(pre));dis2=dis+n;pre2=pre+n;dis[s]=0;while(!q.empty()){intaa=q.top().second;q.pop();if(vis[aa])continue;vis[aa]=true;inta=aa%n;for(inte=head[a];e;e=nxt[e]){intb=to[e],c=w[e];if(aa<n){if(!upd(a,b,dis[a]+c,q))___④__;}else{upd(n+a,n+b,dis2[a]+c,q);}}}voidout(inta){if(a!=s){if(a<n)out(pre[a]);elseout(___⑤___);}printf("%d%c",a%n+1," \n"[a==n+t]);}intmain(){scanf("%d%d%d%d",&n,&m,&s,&t);s--,t--;for(inti=0;i<m;++i){inta,b,c;scanf("%d%d%d",&a,&b,&c);add(a-1,b-1,c);}solve();if(dis2[t]==inf)puts("-1");else{printf("%d\n",dis2[t]);out(n+t);}}- ① 处应填（ ）
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
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、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<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
