发布时间：2025-06-24 19:39:50 作者：北方职教升学中心 阅读量：063
题目大意
给出 n n n个顶点 m m m条长度在 1 1 1~ 5000 5000 5000的边的图，求图中从 1 到 n n n与最短路的路径可重复的严格次短路。
由于，原方案求解的是次短路径长度。非严格次短路已经求解//直接枚举所有边进行松弛操作可求解严格次短路。或者在求解次短路的过程中，一边求最短路径。（严格的含义是，一定比最短路要长，不能相等）
分析
我们先将问题简单化，如何去求一个非严格的次短路呢？设次短路径为 { 1 , a 1 , a 2 , . . . , a k , n } \{1,a_1,a_2,...,a_k,n} {1,a1,a2,...,ak,n}
当 a k = i a_k=i ak=i时，方案变为 { 1 , a 1 , a 2 , . . . , a k − 1 , i , n } \{1,a_1,a_2,...,a_{k-1},i,n\} {1,a1,a2,...,ak−1,i,n}
方案的属性：
- 路径长度 = 子方案路径长度 + w ( i , n ) w(i,n) w(i,n)。得到松弛递推式
d i s t 2 [ n ] = min ( d i s t 2 [ n ] , d i s t [ i ] + w ( i , n ) , d i s t 2 [ i ] + w ( i , n ) ) ，同时保证不与最短路同等路径 dist2[n]=\min(dist2[n],dist[i]+w(i,n),dist2[i]+w(i,n))，同时保证不与最短路同等路径 dist2[n]=min(dist2[n],dist[i]+w(i,n),dist2[i]+w(i,n))，同时保证不与最短路同等路径
因此，在求解次短路之前，要先求解最短路径。根据，正权边的限制可知，次短路径长度长的问题都是由次短路径长度短的问题递推而来。for(intj =0;j <v[i].size();j++){edge k =v[i][j];intto =k.to,val =k.val;if(dist[to]!=dist2[to]){dist3[to]=dist2[to];continue;}if(dist[to]!=dist[i]+val){dist3[to]=min(dist3[to],dist[i]+val);}if(dist[to]!=dist2[i]+val){dist3[to]=min(dist3[to],dist2[i]+val);}}}}signedmain(){cin >>n >>m;for(inti =1;i <=m;i++){intx,y,w;cin >>x >>y >>w;v[x].push_back({y,w,++id});v[y].push_back({x,w,++id});}dij();dij2();dij3();cout <<dist3[n]<<endl;return0;}
非严格次短路 写法 1：
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN =1e5+10;structnode{intto,val;booloperator<(constnode &p)const{returnval >p.val;}};structedge{intto,val,id;};vector<edge>v[N];intn,m,id;intdist[N],flag[N],pre[N];//pre 数组用于记录最短路是用哪条边松弛的voiddij(){priority_queue<node>q;for(inti =1;i <=n;i++)flag[i]=0,dist[i]=1e9;q.push({1,0});dist[1]=0;while(q.size()){node p =q.top();q.pop();if(flag[p.to])continue;flag[p.to]=1;for(inti =0;i <v[p.to].size();i++){edge j =v[p.to][i];if(dist[j.to]>p.val +j.val){dist[j.to]=p.val +j.val;pre[j.to]=j.id;q.push({j.to,dist[j.to]});}}}}intdist2[N];voiddij2(){priority_queue<node>q;for(inti =1;i <=n;i++)flag[i]=0,dist2[i]=1e9;for(inti =1;i <=n;i++)q.push({i,0});//由于并不知道哪个次短路最短，所以将所有的顶点加入到图中，先都求解一遍相应的次短路while(q.size()){node p =q.top();q.pop();if(flag[p.to]==2)continue;// 第二次开始跑次短路flag[p.to]++;for(inti =0;i <v[p.to].size();i++){edge j =v[p.to][i];if(dist2[j.to]>dist[p.to]+j.val &&j.id !=pre[j.to]){// 判断不是最短路 dist2[j.to]=dist[p.to]+j.val;q.push({j.to,dist2[j.to]});}if(dist2[j.to]>dist2[p.to]+j.val){dist2[j.to]=dist2[p.to]+j.val;q.push({j.to,dist2[j.to]});}}}}signedmain(){cin >>n >>m;for(inti =1;i <=m;i++){intx,y,w;cin >>x >>y >>w;v[x].push_back({y,w,++id});// id 给边一个编号v[y].push_back({x,w,++id});}dij();dij2();cout <<dist2[n]<<endl;return0;}非严格次短路 写法 2
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN =1e5+10;structnode{intto,val,now;//now 1/2 代表当前是最短路还是次短路 booloperator<(constnode &p)const{returnval >p.val;}};structedge{intto,val;};vector<edge>v[N];intn,m,id;intdist[N][4],flag[N][4];voiddij(){priority_queue<node>q;for(inti =1;i <=n;i++)flag[i][1]=flag[i][2]=0,dist[i][1]=dist[i][2]=1e9;q.push({1,0,1});dist[1][1]=0;while(q.size()){node p =q.top();q.pop();if(flag[p.to][p.now])continue;// cout << p.to << " " << p.now << " " << p.val << "GGGG"<< endl;flag[p.to][p.now]=1;for(inti =0;i <v[p.to].size();i++){edge j =v[p.to][i];if(dist[j.to][1]>=p.val +j.val){dist[j.to][2]=dist[j.to][1];dist[j.to][1]=p.val +j.val;q.push({j.to,dist[j.to][1],1});q.push({j.to,dist[j.to][2],2});// 不要忘记加入到有优先队列，因为其他次短路可能由该次短路更新}elseif(dist[j.to][2]>p.val +j.val){dist[j.to][2]=p.val +j.val;q.push({j.to,dist[j.to][2],2});}}}}signedmain(){cin >>n >>m;for(inti =1;i <=m;i++){intx,y,w;cin >>x >>y >>w;v[x].push_back({y,w});v[y].push_back({x,w});}dij();cout <<dist[n][2]<<endl;return0;}严格次短路
而如何去求解非严格最短路呢？只需要将松弛式修改为
d i s t 3 [ n ] = min ( d i s t 3 [ n ] , d i s t [ i ] + w ( i , n ) , d i s t 2 [ i ] + w ( i , n ) ) ，同时保证不与最短路长度相同即可 dist3[n]=\min(dist3[n],dist[i]+w(i,n),dist2[i]+w(i,n))，同时保证不与最短路长度相同即可 dist3[n]=min(dist3[n],dist[i]+w(i,n),dist2[i]+w(i,n))，同时保证不与最短路长度相同即可
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN =1e5+10;structnode{intto,val;booloperator<(constnode &p)const{returnval >p.val;}};structedge{intto,val,id;};vector<edge>v[N];intn,m,id;intdist[N],flag[N],pre[N];voiddij(){priority_queue<node>q;for(inti =1;i <=n;i++)flag[i]=0,dist[i]=1e9;q.push({1,0});dist[1]=0;while(q.size()){node p =q.top();q.pop();if(flag[p.to])continue;flag[p.to]=1;for(inti =0;i <v[p.to].size();i++){edge j =v[p.to][i];if(dist[j.to]>p.val +j.val){dist[j.to]=p.val +j.val;pre[j.to]=j.id;q.push({j.to,dist[j.to]});}}}}intdist2[N];voiddij2(){priority_queue<node>q;for(inti =1;i <=n;i++)flag[i]=0,dist2[i]=1e9;for(inti =1;i <=n;i++)q.push({i,0});while(q.size()){node p =q.top();q.pop();if(flag[p.to]==2)continue;flag[p.to]++;for(inti =0;i <v[p.to].size();i++){edge j =v[p.to][i];if(dist2[j.to]>dist[p.to]+j.val &&j.id !=pre[j.to]){// 并且不是最短路 dist2[j.to]=dist[p.to]+j.val;q.push({j.to,dist2[j.to]});}if(dist2[j.to]>dist2[p.to]+j.val){dist2[j.to]=dist2[p.to]+j.val;q.push({j.to,dist2[j.to]});}}}}intdist3[N];voiddij3(){for(inti =1;i <=n;i++)flag[i]=0,dist3[i]=1e9;for(inti =1;i <=n;i++){//由于最短路、那么子方案路径长度有可能是最短路径或次短路径。
