【题目】CSP-S 2024 提高级 第一轮初赛 完善程序2(2)次短路已知一个n个点m条边的有向图G并且给定图中的两个点s和t求次短路长度严格大于最短路的最短路径。如果不存在输出一行“-1”。如果存在输出两行第一行表示次短路的长度第二行表示次短路的一个方案。#includecstdio#includequeue#includeutility#includecstringusingnamespacestd;constintmaxn2e510,maxm1e610,inf522133279;intn,m,s,t;inthead[maxn],nxt[maxm],to[maxm],w[maxm],tot1;intdis[maxn1],*dis2;intpre[maxn1],*pre2;boolvis[maxn1];voidadd(inta,intb,intc){tot;nxt[tot]head[a];to[tot]b;w[tot]c;head[a]tot;}boolupd(inta,intb,intd,priority_queuepairint,intq){if(ddis[b])returnfalse;if(bn)___(1)___;q.push(___(2)___);dis[b]d;pre[b]a;returntrue;}voidsolve(){priority_queuepairint,intq;q.push(make_pair(0,s));memset(dis,___(3)___,sizeof(dis));memset(pre,-1,sizeof(pre));dis2disn;pre2pren;dis[s]0;while(!q.empty()){intaaq.top().second;q.pop();if(vis[aa])continue;vis[aa]true;intaaa%n;for(intehead[a];e;enxt[e]){intbto[e],cw[e];if(aan){if(!upd(a,b,dis[a]c,q))___(4)___}else{upd(na,nb,dis2[a]c,q);}}}}voidout(inta){if(a!s){if(anout(pre[a]);elseout(___(5)___);}printf(%d%c,a%n1, \n[ant]);}intmain(){scanf(%d%d%d%d,n,m,s,t);s--,t--;for(inti0;im;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(nt);}return0;}(1)处应填 A.udp(pre[b],nb,dis[b],q)B.upd(a,nb,d,q)C.upd(pre[b],b,dis[b],q)D.upd(a,b,d,q)(2)处应填 A.make_pair(-d,b)B.make_pair(d,b)C.make_pair(b,d)D.make_pair(-b,d)(3)处应填 A.0xffB.0x1fC.0x3fD.0x7f(4)处应填 A.upd(a,nb,dis[a]c,q)B.upd(na,nb,dis2[a]c.q)C.upd(na,b,dis2[a]c,q)D.upd(a,b,dis[a]c,q)(5)处应填 A.pre2[a%n]B.pre[a%n]C.pre2[a]D.pre[a%n]1【题目考点】1. 图论次短路径2. 图论最短路 Dijkstra堆优化【解题思路】intmain(){scanf(%d%d%d%d,n,m,s,t);s--,t--;for(inti0;im;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(nt);}return0;}输入顶点数n边数m起点s终点ts和t都减1以及下面添加边时传入a-1, b-1表示该题输入时顶点编号为1~n而代码内顶点编号从0~n-1。循环m次每次循环输入一条边表示存在有向边a, b权值为c。voidadd(inta,intb,intc){tot;nxt[tot]head[a];to[tot]b;w[tot]c;head[a]tot;}add函数的链式前向星实现邻接表的常规操作tot为链表中用到的最大结点地址nxt[i]表示地址为i的结点的下一个结点的地址to[i]表示地址为i的结点上的顶点编号w[i]表示地址为i的结点上的边的权值。head[a]表示顶点a后面的单链表中第一个结点的地址。主函数中线调用solve函数而后如果dist2[t]为inf也就是没有找到从起点s到终点t的严格次短路则输出-1。否则输出起点s到终点t的严格次短路的长度dist2[t]再通过out函数输出次短路的路径。voidsolve(){priority_queuepairint,intq;q.push(make_pair(0,s));memset(dis,___(3)___,sizeof(dis));memset(pre,-1,sizeof(pre));dis2disn;pre2pren;dis[s]0;}solve函数的Dijkstra堆优化的模板。优先队列q中保存数对(first, second)的意义是存在到顶点second的长为first的路径。首先存在到顶点s的长为0的路径因此把数对(s, 0)加入优先队列。优先队列的默认比较规则为less仿函数该函数传入a、b两个优先队列中的元素返回ab其意义为当满足ba时b更优先优先级最高的元素在优先队列的堆顶。pair类型已重载运算符比较方式是先比较第一个属性first再比较第二个属性seond。先比较的first属性表示路径长度first的值越大越优先。而作为求最短路的算法应该是路径长度越小越优先。为了解决这一点可以取路径长度的相反数作为pair对象的first属性first作为负值越大表明first的相反数越小。这样虽然优先队列是大顶堆但维护的实际是已知的路径长度最小的路径。intdis[maxn1],*dis2;intpre[maxn1],*pre2;...dis2disn;pre2pren;根据dis数组长度为2*maxn以及dis2实际指向dis[n]可知dis[0]~dis[n-1]中dis[i]保存的是从s出发到i的最短路径长度。dis[n]~dis[2*n-1]也就是dis2[0]~dis2[n]中dis2[i]表示的是从s出发到i的严格次短路径。同理pre[n]~pre[2*n-1]也就是pre2[0]~pre2[n]pre[i]是顶点从s到i的最短路径上i的前一个顶点。pre2[i]是顶点从s到i的严格次路径上i的前一个顶点。主函数中dis2[t]和inf比较可知dis2数组也就是dis数组的初值为inf。inf的值为522133279第(3)空每字节的值根据选项可能为0xff0x1f, 0x3f, 0x7f经过memset后int类型dis数组中每个元素的值为4字节如每字节的值为0xff元素的初值为0xffffffff如每字节的值为0x1f元素的初值为0x1f1f1f1f如每字节的值为0x3f元素的初值为0x3f3f3f3f如每字节的值为0x7f元素的初值为0x7f7f7f7f元素初值的区别在十六进制下的右边数第2位要想得到这一位的数字需要将元素值先整除16再模16。⌊52213327916⌋mod 161\lfloor \frac{522133279}{16}\rfloor \mod161⌊16522133279​⌋mod161所以每字节的值为0x1f第(3)空选B。pre初值都设为-1。while(!q.empty()){intaaq.top().second;q.pop();if(vis[aa])continue;vis[aa]true;intaaa%n;for(intehead[a];e;enxt[e]){intbto[e],cw[e];if(aan){if(!upd(a,b,dis[a]c,q))___(4)___}else{upd(na,nb,dis2[a]c,q);}}}vis[i]的意义是顶点i是否已出队。如果ininin说明出队的路径是从源点到顶点i的最短路径。如果到顶点iii的最短路径已经出队路径长度为ddd。后续再出队的到顶点iii的最短路径的路径长度为d′dd′则一定有d′≥dd\ge dd′≥d使用d′dd′更新到顶点iii的邻接点的路径长度不如使用ddd更新到顶点iii的邻接点的路径得到的路径长度更短。在ininin的情况下该路径也不被作为到顶点iii的次短路径看待因为如果是次短路会设为i≥ni\ge ni≥n。如果i≥ni \ge ni≥n说明出队的路径是从源点到顶点i的次短路径。同理第二次出队的到顶点iii的次短路路径不如第一次出队的次短路路径能更好地更新到其邻接点的次短路径。因此如果堆顶元素中second是已经出队的顶点就不再更新到其邻接点的最短或次短路径。这就是为什么有if(vis[aa]) continue;因为aa可能是大于等于n用来表示次短路的顶点编号所以先进行a aa%n把aa处理成其对应的真正顶点编号a。遍历a的邻接点b是a的一个邻接点c是便a, b的权值。如果aan说明从优先队列出队的是一条从起点s到a的最短路径这样的路径可以更新最短路以及次短路。否则如果aan那么从优先队列出队的是一条从起点s到a的次短路径这样的路径只可能更新次短路径。更新次短路的核心思路为如果新路径比最短路径短更短那么原最短路变为次短路新路径作为最短路。否则如果新路径比严格次短路短但是比最短路长那么新路径作为严格次短路。boolupd(inta,intb,intd,priority_queuepairint,intq){if(ddis[b])returnfalse;if(bn)___(1)___;q.push(___(2)___);dis[b]d;pre[b]a;returntrue;}upd的意思是update更新。结合调用语句upd(a, b, dis[a] c, q)可知参数a、b、d的意义是从存在一条从起点s到b的长为d的路径最后一步是从a走到b的。参数q是优先队列的引用一直传q即可。如果新路径长度d比已有的路径长度dis[b]可能是最短或次短路更长则不发生更新返回false。如果终点bn则当前到b新路径比到b的最短路长度更小需要使用当前的最短路长度dis[b]更新到b的次短路长度dis2[b]实现方法为再次调用upd函数参数a填路径上b的前一个顶点pre[b]参数b填b参数d为dis[b]所以第(1)空填udp(pre[b],nb,dis[b],q)选A。无论bn时dis[b]表示最短路还是bn时dis[b]表示次短路都需要使用新的到顶点b的长为d的路径来更新自己。前文提过在优先队列中保存的pair的first属性应该是路径长度的相反数second属性为到达顶点。因此第(2)空填make_pair(-d, b)选A。接下来将到顶点b的距离更新为d路径上b的前一个顶点设为a。只要成功更新路径就返回true。if(aan){if(!upd(a,b,dis[a]c,q))___(4)___}else{upd(na,nb,dis2[a]c,q);}如果upd(a, b, dis[a] c, q)返回假也就是到顶点b的路径长度dis[a]c大于等于最短路dis[b]不能更新最短路那么尝试更新次短路。调用upd函数更新到顶点b的次短路前一个顶点是a第一个参数传a。到b的次短路长度保存在dis[bn]因此第二个参数传bn路径长度为dis[a]c。因此第(4)空填upd(a, bn, dis[a]c, q)选A。如果aan则出队的路径是个次短路径只能更新次短路径此时到达的顶点为nb其前一个顶点为aa也就是an。新的路径长度为dis[an]c也就是dis2[a]c。调用solve函数完成Dijkstra堆优化算法求出了dis数组其中包含到每个顶点的最短路和次短路的信息pre数组保存了到每个顶点的最短路和次短路上该顶点的前一个顶点。voidout(inta){if(a!s){if(anout(pre[a]);elseout(___(5)___);}printf(%d%c,a%n1, \n[ant]);}如果存在从s到t的次短路最后输出次短路长度和次短路径。先看输出语句a % n 1是无论an还是ana%n都将a处理成其表示的顶点编号再加1是因为原题目中顶点编号从1~n而代码中顶点编号从0~n-1。 \n[a n t]是一种很诡异的写法 \n相当于char s[2] { , \n}中的s。当a ! nt时 \n[0]就是s[0]是 。当a nt时也就是传入的a是次短路的终点t时 \n[1]就是s[1]是\n。如果as则是递归出口只做输出。如果a!s输出从起点s到a的次短路径就是先输出从起点s到a的前一个顶点pre[a]的次短路径再输出顶点a。调用out(pre[a])就可以输出从起点s到a的前一个顶点pre[a]的次短路径无论a是否小于npre[a]都保存了次短路径上a的前一个顶点。当an时调用了out(pre[a])当an时也应该调用out(pre[a])但是没有这个选项看一看有没有等价的选项。pre[a] pre[a-nn] pre2[a-n] pre2[a%n]因此第(5)空填pre2[a%n]选A。【答案】AABAA