P1941集合位置 「次短路题解」

题目链接

P1941集合位置

题意总结

• 让您求非严格次短路，也就是如果有多条最短路，次短路等于最短路。
• 当然如果您想要写A*的K短路也是可以的，只不过代码量较大而已。
• 开始我是维护的dis1和dis2，分别记录最短和次短，搞一下转移，只需一遍spfa即可，但是这只能求严格次短路，因为如果涉及到非严格的话，转移很混乱，比如根节点多次进队列等等。
• 于是我们换一种思路，记录一下1～n最短路上每条边，依次只删一条边，然后去跑1～n的最短路，ans记录跑出来的最小值，最终ans即为所求。
• 借助了一点点贪心思想，可以自己举反例，应该能理解。（如果有问题，可以在评论里留言）

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <deque>
using namespace std;
const int maxn=205;
const double E=1e-6;
double x[maxn],y[maxn],dis[maxn],ans=1e10;
int n,m,cnt,head[maxn],la[maxn];
bool vis[maxn];
struct Edge{int from,to,next;double val;}e[maxn*maxn/2+5];
double DIS(int a,int b){
	return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
void A(int x,int y,double z){
	e[++cnt].to=y;
	e[cnt].val=z;
	e[cnt].next=head[x];
	e[cnt].from=x;
	head[x]=cnt;
}
deque<int> q;//双端队列优化spfa，写习惯了
void spfa(bool st){//st是1则说明这次需要处理la数组记录最短路上的边，是0就不需记录
	for(int i=1;i<=n;++i)dis[i]=1e10,vis[i]=0;
	dis[1]=0;vis[1]=1;
	q.push_back(1);
	while(!q.empty()){
		int x=q.front();q.pop_front();
		vis[x]=0;
		for(int i=head[x],y;i;i=e[i].next){
			y=e[i].to;
			if(dis[y]>dis[x]+e[i].val){
				if(st)la[y]=i;//如果能被更新，说明这是目前最短路中的一条边
				dis[y]=dis[x]+e[i].val;
				if(!vis[y]){
					vis[y]=1;
					if(!q.empty()&&dis[y]<=dis[q.front()])q.push_front(y);//双端队列操作
					else q.push_back(y);//双端队列操作
				}
			}
		}
	}
}	
int main(){
//	freopen("1.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%lf%lf",&x[i],&y[i]);
	double z;
	for(int i=1,x,y;i<=m;++i){
		scanf("%d%d",&x,&y);
		z=DIS(x,y);
		A(x,y,z);A(y,x,z);
	}
	spfa(1);
	double res;
	for(int i=la[n];i;i=la[e[i].from]){
		res=e[i].val;//记录下要删掉边的权值，保存一下防丢
		e[i].val=1e10;//删掉最短路中的一条边
		spfa(0);
		ans=min(ans,dis[n]);//记录，更新ans
		e[i].val=res;//借助res，恢复这条边
	}
	if(ans==1e10)printf("-1\n");//1～n没有次短路
	else printf("%.2lf\n",ans);
	return 0;
}

P1941集合位置 「次短路题解」

原文：https://www.cnblogs.com/Lour688/p/13325189.html