【校内模拟】次短路

次短路模板

题目描述：

(n)个点和(m)条边的无向图，每条边都有边权，

次短路的长度须严格大于最短路（可以有多条）的长度，同时又不大于所有除最短路外的道路的长度。

求次短路的长度

当时我没怎么想，直接(A*)搜索，过了样例，(However)，我把(fclose)加在了(printf)后面，爆零

之后自己测了一遍，得了(90)分（(WA)了一个点）

看了题解以后，我内心是拒绝的

直接爆搜加上一个看上去很(low)的剪枝

然而，旁边的(dalao)说他求两遍最短路，枚举边，(AC)了

好像这才是正解啊

(90)分(A*)：

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<queue>
using namespace std;
#define N 5010
#define M 200010
int n,m;
inline int read(){
	int x=0; char c=getchar();
	while(c<'0') c=getchar();
	while(c>='0') x=(x<<3)+(x<<1)+c-'0',c=getchar();
	return x;
}
int Head[N],num;
struct NODE{
	int to,next,w;
} e[M];
inline void add(int x,int y,int w){
	e[++num].to=y;
	e[num].w=w;
	e[num].next=Head[x];
	Head[x]=num;
}
int dis[N];
bool used[N];
queue<int> q;
inline void SPFA(){
	memset(dis,0x3f,sizeof(dis));
	dis[n]=0;
	q.push(n);
	while(!q.empty()){
		int u=q.front();q.pop();
		used[u]=0;
		for(int i=Head[u];i;i=e[i].next){
			int v=e[i].to;
			if(dis[v]<=dis[u]+e[i].w)continue;
			dis[v]=dis[u]+e[i].w;
			if(!used[v]){
				q.push(v);
				used[v]=1;
			}
		}
	}
}
struct HA{
	int pos,cost;
};
struct cmp{
	bool operator ()(HA a,HA b){
		return dis[a.pos]+a.cost>dis[b.pos]+b.cost;
	}
};
int minn;
priority_queue<HA,vector<HA>,cmp > que;
inline void A_star(){
	minn=dis[1];
	que.push(HA{1,0});
	while(!que.empty()){
		HA u=que.top(); que.pop();
		if(u.pos==n){
			if(u.cost>minn){
				printf("%d
",u.cost);
				fclose(stdin); fclose(stdout);
				exit(0);
			}
			continue;
		}
		for(int i=Head[u.pos];i;i=e[i].next)
			que.push(HA{e[i].to,u.cost+e[i].w});
	}
}
int main()
{
	freopen("maze.in","r",stdin);
	freopen("maze.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y,z;
	for(int i=1;i<=m;i++){
		x=read(); y=read(); z=read();
		add(x,y,z); add(y,x,z);
	}
	SPFA();
	A_star();
	return 0;
}

正解：

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<queue>
using namespace std;
#define N 5010
#define M 200010
int n,m,ans=0x7fffffff;
inline int read(){
	int x=0; char c=getchar();
	while(c<'0') c=getchar();
	while(c>='0') x=(x<<3)+(x<<1)+c-'0',c=getchar();
	return x;
}
int Head[N],num;
struct NODE{
	int to,next,w;
} e[M];
inline void add(int x,int y,int w){
	e[++num].to=y;
	e[num].w=w;
	e[num].next=Head[x];
	Head[x]=num;
}
int dis1[N],disn[M];
bool used[N];
queue<int> q;
inline void SPFA1(){
	memset(dis1,0x3f,sizeof(dis1));
	dis1[1]=0;
	q.push(1);
	while(!q.empty()){
		int u=q.front();q.pop();
		used[u]=0;
		for(int i=Head[u];i;i=e[i].next){
			int v=e[i].to;
			if(dis1[v]<=dis1[u]+e[i].w)continue;
			dis1[v]=dis1[u]+e[i].w;
			if(!used[v]){
				q.push(v);
				used[v]=1;
			}
		}
	}
}
inline void SPFA2(){
	memset(disn,0x3f,sizeof(disn));
	disn[n]=0;
	q.push(n);
	while(!q.empty()){
		int u=q.front();q.pop();
		used[u]=0;
		for(int i=Head[u];i;i=e[i].next){
			int v=e[i].to;
			if(disn[v]<=disn[u]+e[i].w)continue;
			disn[v]=disn[u]+e[i].w;
			if(!used[v]){
				q.push(v);
				used[v]=1;
			}
		}
	}
}
int main()
{
	freopen("maze.in","r",stdin);
	freopen("maze.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y,z;
	for(int i=1;i<=m;i++){
		x=read(); y=read(); z=read();
		add(x,y,z); add(y,x,z);
	}
	SPFA1();
	SPFA2();
	for(int i=1;i<=n;i++)
		for(int j=Head[i];j;j=e[j].next){
			int t=dis1[i]+disn[e[j].to]+e[j].w;
			if(t!=dis1[n]&&t<ans)
				ans=t;
	}
	printf("%d
",ans);
	return 0;
}