P2829 大逃离
2019-08-19

题目背景

zrz走进了一个奇葩的迷宫,他发现自己迷路了,想逃出来,他好不容易数完了所有的路,累的快晕了,只好叫你帮忙咯。

题目描述

这是一棵有n个节点的图,有m条双向边,每一条路有w个单位距离,zrz在1的位置,出口在n的位置,不过zrz脑子出了点bug,于是不想走最短的路,想走第2短的路,第2短路径允许与最短路径有重边,然后也可以重复通过一些节点和路,注意如果有多条路径都是最短路径,那么他们都不能叫第2短路径。但是zrz觉得如果接下来进入的一个节点所直接连接的地方小于k个(起点和终点除外),那么他就不敢进去。

原题链接

Solve

1.次短路问题+SPFA。

2.设起点为s,终点t。

3.设dis1[i]为s到节点i的最短路,dis2[i]为t到节点2的最短路。

4.设次短路ans。

5.ans即为min{dis1[u]+w+dis2[v]}(u,v,w表示每条边的两侧端点和权值),ans!=dis1[t]。

Tip

1.蒟蒻的我并不会证明该过程的正确性。

2.直接连接的地方小于k个,此处指的是点数。

Code


#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define N 400010
using namespace std;  //标准开头
int n,m,k;  //同题
int e,r,dist;  //输入时的端点,权值
int ans=1e9;  //答案
int du[N];  //直接连接的点数
int dis1[N],dis2[N];  //同Solve
int first[N],next[N],len;  //邻接表,len表示边数
bool vis[N];
int f[5001][5001];  //f[i][j]>0,表示i与j直接相连
struct note{  //邻接表
	int u,v,w;
}d[N];
void add(int e,int r,int dist){  //邻接表
	d[++len].u=e;
	d[len].v=r;
	d[len].w=dist;
	next[len]=first[e];
	first[e]=len;
}
void spfa(int s,int *dis){  //标准SPFA
	memset(vis,false,sizeof(vis));
	dis[s]=0;
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		int e=q.front();
		q.pop();
		vis[e]=false;
		for(int i=first[e];i!=-1;i=next[i]){
			if(du[d[i].v]<k&&d[i].v!=1&&d[i].v!=n) continue;  //排除度数小于k
			if(dis[d[i].v]>dis[e]+d[i].w){
				dis[d[i].v]=dis[e]+d[i].w;
				if(!vis[d[i].v]){
					vis[d[i].v]=true;
					q.push(d[i].v);
				}
			}
		}
	}
}
int main()
{
	memset(first,-1,sizeof(first));
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) dis1[i]=dis2[i]=1e9;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&e,&r,&dist);
		f[e][r]++;
		f[r][e]++;
		add(e,r,dist);
		add(r,e,dist);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) if(f[i][j]) du[i]++;
	}
	spfa(1,dis1);
	spfa(n,dis2);
	for(int i=1;i<=len;i++){
		if(dis1[d[i].u]+d[i].w+dis2[d[i].v]!=dis1[n]&&ans>dis1[d[i].u]+d[i].w+dis2[d[i].v]) ans=dis1[d[i].u]+d[i].w+dis2[d[i].v]; 
	}
	if(ans==1e9) printf("-1");
	else printf("%d",ans);
	return 0; 
}