P2865 [USACO06NOV] Roadblocks G 与最短路的路径可重复的严格次短路

题目大意

给出 $n$ 个顶点 $m$ 条长度在 $1$ ~ $5000$ 的边的图，求图中从 1 到 $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$ 时，方案变为 { 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}
方案的属性：

1. 路径长度 = 子方案路径长度 + $w(i,n)$。
2. 路径的目的地。

由于，原方案求解的是次短路径长度。那么子方案路径长度有可能是最短路径或次短路径。得到松弛递推式
$$dist2[n]=\min (dist2[n],dist[i]+w(i,n),dist2[i]+w(i,n))，同时保证不与最短路同等路径$$
因此，在求解次短路之前，要先求解最短路径。或者在求解次短路的过程中，一边求最短路径。

根据，正权边的限制可知，次短路径长度长的问题都是由次短路径长度短的问题递推而来。因此，也可以使用 dijkstra 的递推贡献式求解方法。

非严格次短路 写法 1：

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5 + 10;


struct node{
	int to,val;
	bool operator <(const node &p)const{
		return val > p.val;
	}
};

struct edge{
	int to,val,id;
};
vector<edge> v[N];

int n,m,id;
int dist[N],flag[N],pre[N]; //pre 数组用于记录最短路是用哪条边松弛的
void dij(){
	priority_queue<node>q;
	for(int i = 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(int i = 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]});
			}
		}	
	}	
}

int dist2[N];
void dij2(){
	priority_queue<node>q;
	for(int i = 1; i <= n; i++) flag[i] = 0,dist2[i] = 1e9;
	
	for(int i = 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(int i = 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]});
			}
		}	
	}	
}
signed main(){ 
	
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int x,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;
	
	
	return 0;
}

非严格次短路 写法 2

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5 + 10;


struct node{
	int to,val,now; //now 1/2 代表当前是最短路还是次短路 
	bool operator <(const node &p)const{
		return val > p.val;
	}
};

struct edge{
	int to,val;
};
vector<edge> v[N];

int n,m,id;
int dist[N][4],flag[N][4];
void dij(){
	priority_queue<node>q;
	for(int i = 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(int i = 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}); // 不要忘记加入到有优先队列，因为其他次短路可能由该次短路更新
			}else if(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});
			}
		}	
	}	
}

signed main(){ 
	
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int x,y,w;
		cin >> x >> y >> w;
		v[x].push_back({y,w});
		v[y].push_back({x,w});
	}
	
	dij();

	cout << dist[n][2] << endl;
	
	
	return 0;
}

严格次短路

而如何去求解非严格最短路呢？只需要将松弛式修改为
$$dist3[n]=\min (dist3[n],dist[i]+w(i,n),dist2[i]+w(i,n))，同时保证不与最短路长度相同即可$$

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5 + 10;


struct node{
	int to,val;
	bool operator <(const node &p)const{
		return val > p.val;
	}
};

struct edge{
	int to,val,id;
};
vector<edge> v[N];

int n,m,id;
int dist[N],flag[N],pre[N];
void dij(){
	priority_queue<node>q;
	for(int i = 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(int i = 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]});
			}
		}	
	}	
}

int dist2[N];
void dij2(){
	priority_queue<node>q;
	for(int i = 1; i <= n; i++) flag[i] = 0,dist2[i] = 1e9;
	
	for(int i = 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(int i = 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]});
			}
		}	
	}	
}

int dist3[N];
void dij3(){
	for(int i = 1; i <= n; i++) flag[i] = 0,dist3[i] = 1e9;
	for(int i = 1; i <= n; i++){ //由于最短路、非严格次短路已经求解
								//直接枚举所有边进行松弛操作可求解严格次短路。
		for(int j = 0; j < v[i].size(); j++){
			edge k = v[i][j];
			int to = 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);
			}
		}
	}
}

signed main(){ 
	
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int x,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;
	
	
	return 0;
}