洛谷 P2829 大逃离（最短路）

传送门

---

解题思路

对于这种求次短路的题，很常见的套路是先求出以起点和终点作为源点到其他各点的单源最短路，然后枚举每一条边，可以发现次短路一定是重复经过某一条边或者走了这条不在最短路中的边。分类讨论即可。

注意本题中有重边和自环，且计算度时，重边算一次，自环也算。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
using namespace std;
const int maxn=100005;
struct node{
	int u,v,next,w;
}e[maxn*2];
int n,m,k,in[maxn],cnt,p[maxn],dis1[maxn],dis2[maxn],ans;
map<pair<int,int>,int> ma;
set<pair<int,int> > q;
void insert(int u,int v,int w){
	cnt++;
	e[cnt].u=u;
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=p[u];
	p[u]=cnt;
}
void dij1(int s){
	memset(dis1,0x3f,sizeof(dis1));
	dis1[s]=0;
	q.insert(make_pair(0,s));
	while(!q.empty()){
		int u=q.begin()->second;q.erase(q.begin());
		if(u!=1&&u!=n&&in[u]<k) continue;
		for(int i=p[u];i!=-1;i=e[i].next){
			int v=e[i].v;
			if(dis1[v]>dis1[u]+e[i].w){
				q.erase(make_pair(dis1[v],v));
				dis1[v]=dis1[u]+e[i].w;
				q.insert(make_pair(dis1[v],v));
			}
		}
	}
}
void dij2(int s){
	memset(dis2,0x3f,sizeof(dis2));
	dis2[s]=0;
	q.insert(make_pair(0,s));
	while(!q.empty()){
		int u=q.begin()->second;q.erase(q.begin());
		if(u!=1&&u!=n&&in[u]<k) continue;
		for(int i=p[u];i!=-1;i=e[i].next){
			int v=e[i].v;
			if(dis2[v]>dis2[u]+e[i].w){
				q.erase(make_pair(dis2[v],v));
				dis2[v]=dis2[u]+e[i].w;
				q.insert(make_pair(dis2[v],v));
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	memset(p,-1,sizeof(p));
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){//有重边、自环 ！！ 
		int u,v,w;
		cin>>u>>v>>w;
		if(ma.find(make_pair(u,v))==ma.end()){
			in[u]++;in[v]++;
			if(u==v) in[u]--;
			ma[make_pair(u,v)]=1;
			ma[make_pair(v,u)]=1;
		}
		insert(u,v,w);
		insert(v,u,w);
	}
	dij1(1);
	dij2(n);
	ans=0x3f3f3f3f;
	for(int i=1;i<=cnt;i++){
		int u=e[i].u,v=e[i].v;
		if((u!=1&&u!=n&&in[u]<k)||(v!=1&&v!=n&&in[v]<k)) continue;
		int d=dis1[u]+e[i].w+dis2[v];
		if(d==dis1[n]){
			if(d+e[i].w*2<ans) ans=d+e[i].w*2;
		}else{
			if(ans>d) ans=d;
		}
		if(dis1[u]+dis2[u]+e[i].w*2<ans) ans=dis1[u]+dis2[u]+e[i].w*2;
		if(dis1[v]+dis2[v]+e[i].w*2<ans) ans=dis1[v]+dis2[v]+e[i].w*2;
	}
	if(ans!=0x3f3f3f3f) cout<<ans;
	else cout<<-1;
	return 0;
}