SCU 4444 Travel 【次完全圖最短路】

vjudge題面位址

SOL

對于 a &lt; b   a n d   L i n k [ 1 ] [ n ] = = 0 a&lt;b\ and\ Link[1][n]==0 a<b and Link[1][n]==0，對m條邊正向bfs即可；

對于 a &gt; b   a n d   L i n k [ 1 ] [ n ] = = 1 a&gt;b\ and\ Link[1][n]==1 a>b and Link[1][n]==1,顯然不能在 n 2 − m n^2-m n2−m條邊的 b b b圖上直接bfs；

可以把 b b b圖轉化為 m m m 條邊的補集。若用每一個點嘗試更新未更新的點，對于所有點，在 b b b圖不能更新出的點總和是 m . m. m.

那麼建構對點 1 − n 1-n 1−n的雙向連結清單，每次用bfs到的目前 u u u嘗試更新連結清單中的點（記為 v v v)，若能更新，便把 v v v從連結清單中删除。

時間複雜度： O ( n + m ) O(n+m) O(n+m)。證明：若目前成功更新，目前 O ( 1 ) O(1) O(1)，連結清單中少一個點，總共 O ( n ) O(n) O(n)。若不能更新，目前 O ( 1 ) O(1) O(1)，總共最多 m m m次更新失敗，為 O ( m ) O(m) O(m)。

CODE

#include<bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define ll long long
#define cs const
#define db double
#define ri register int
#define gc getchar()
#define in red()
inline int red(){
	int num=0,f=1;char c=gc;
	for(;!isdigit(c);c=gc)if(c=='-')f=-1;
	for(;isdigit(c);c=gc)num=num*10+(c^48);
	return num*f;
}
cs int N=1e5+10,M=1e6+10;
int pre[N],suf[N];
int vis[N],outstk[N],head[N],to[M],nxt[M],a,b,cnt=0,n,m;
ll dis[N];
inline void addedge(int u,int v){
	nxt[++cnt]=head[u];head[u]=cnt;to[cnt]=v;
	nxt[++cnt]=head[v];head[v]=cnt;to[cnt]=u;
}
queue<int> q;
inline ll bfs1(int k){
	q.push(1);vis[1]=1;dis[1]=0;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(ri i=head[u];i;i=nxt[i]){
			int v=to[i];
			if(vis[v])continue;
			vis[v]=1;
			dis[v]=dis[u]+k;
			q.push(v);
		}
	}
	return dis[n];
}
inline void delet(int x){
	suf[pre[x]]=suf[x];
	pre[suf[x]]=pre[x];
}
inline ll bfs2(int k){
	memset(outstk,0,sizeof (outstk));
	for(ri i=1;i<=n+1;++i)pre[i+1]=suf[i-1]=i;
	q.push(1);dis[1]=0;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(ri i=head[u];i;i=nxt[i])vis[to[i]]=1;
		for(ri i=0;i^(n+1);i=suf[i]){
			if(i>1&&!vis[i]&&!outstk[i]){
				dis[i]=dis[u]+k;
				q.push(i);
				delet(i);
				outstk[i]=1;
			}
		}
		for(ri i=head[u];i;i=nxt[i])vis[to[i]]=0;
	}
	return dis[n];
}
signed main(){
//	freopen("data.in","r",stdin);
	while(sf("%d%d%d%d",&n,&m,&a,&b)!=EOF){
		memset(head,0,sizeof (head));
		memset(vis,0,sizeof(vis));
		memset(dis,0x5f,sizeof (dis));
		cnt=0;
		bool f=1;
		for(ri i=1;i<=m;++i){
			int u,v;sf("%d%d",&u,&v);
			if((u==1&&v==n)||(u==n&&v==1))f=0;
			addedge(u,v);
		}
		if(a==b)cout<<a<<'\n';
		else if(a<b){
			if(!f)cout<<a<<'\n';
			else cout<<min(1ll*b,bfs1(a))<<'\n';
		}
		else if(a>b){
			if(!f)cout<<min(1ll*a,bfs2(b))<<'\n';
			else cout<<b<<'\n';
		}
	}
	
	return 0;
}