10pts求助
查看原帖
10pts求助
531930
Southern_Dynasty楼主2022/10/7 11:54

RT.

bfs1 用来搜出连通块,bfs2 标记点是否合法,bfs3 求最短路。

#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma GCC optimize("Ofast")
#define gt getchar
#define pt putchar
#define y1 y233
#define rep(i,a,b,k) for(int (i)=(a),(_)=(b);(i)<=(_);(i)+=(k))
#define per(i,a,b,k) for(int (i)=(a),(_)=(b);(i)>=(_);(i)-=(k))
#define edgerep(i,h,u,e) for(int (i)=h[(u)];(i);(i)=e[(i)].nxt)
typedef long long ll;
//typedef __int128 lll;
typedef unsigned long long ull;
const int N=1e4+5;
const int M=2e5+5;
using namespace std;
//using namespace __gnu_pbds;
inline bool __(char ch){return ch>=48&&ch<=57;}
inline int read(){
   	int x=0;bool sgn=0;char ch=gt();
   	while(!__(ch)){sgn|=(ch=='-');ch=gt();}
   	while(__(ch)){x=(x<<1)+(x<<3)+(ch-'0');ch=gt();}
	return sgn?-x:x;
}
inline void print(int x){
	static char st[70];short top=0;
	if(x<0)pt('-'),x=-x;
    do{st[++top]=(x%10+'0'),x/=10;}while(x);
    while(top)pt(st[top--]);
}
inline void printsp(int x){
	static char st[70];short top=0;
	if(x<0)pt('-'),x=-x;
    do{st[++top]=(x%10+'0'),x/=10;}while(x);
    while(top)pt(st[top--]);pt(32);
}
inline void println(int x){
	static char st[70];short top=0;
	if(x<0)pt('-'),x=-x;
    do{st[++top]=(x%10+'0'),x/=10;}while(x);
    while(top)pt(st[top--]);pt(10);
}
inline void put_str(string s){
	int siz=s.size();
	rep(i,0,siz-1,1) pt(s[i]);
	printf("\n");
}
int n,m,s,t,dis[N];
bool vis[N],vis2[N],unused[N];
struct Graph{
	struct edge{
		int to,nxt;
	}e[M<<1];
	int head[M<<1],cnt,dis[N];
	bool vis[N],vis2[N];
	inline void addedge(int f,int t){
		e[++cnt].to=t;
		e[cnt].nxt=head[f];
		head[f]=cnt;
	}
}G[3];
inline void bfs1(int t){
	queue<int>q;
	q.push(t),vis[t]=1;
	while(q.size()){
		int u=q.front();
		q.pop();
		for(int i=G[0].head[u];i;i=G[0].e[i].nxt){
			int v=G[0].e[i].to;
			if(!vis[v])vis[v]=1,q.push(v);
			G[1].addedge(v,u);
		}
	}
}
inline void bfs2(int s){
	queue<int>q;
	q.push(s);
	while(q.size()){
		int u=q.front();
		q.pop();
		for(int i=G[2].head[u];i;i=G[2].e[i].nxt){
			int v=G[2].e[i].to;
			if(!vis[v]){unused[u]=1;break;}
		}
		if(unused[u])continue;
		for(int i=G[2].head[u];i;i=G[2].e[i].nxt){
			int v=G[2].e[i].to;
			if(unused[v])continue;
			q.push(v);
		}
	}
}
inline void bfs3(int s){
	queue<int>q;
	q.push(s),vis2[s]=1,dis[s]=0;
	while(q.size()){
		int u=q.front();
		q.pop();
		for(int i=G[1].head[u];i;i=G[1].e[i].nxt){
			int v=G[1].e[i].to;
			if(vis2[v]||unused[v])continue;
			dis[v]=dis[u]+1,vis2[v]=1,q.push(v);
		}
	}
}
signed main(){
	n=read(),m=read();
	rep(i,1,m,1){
		int u=read(),v=read();
		G[0].addedge(v,u);
		G[2].addedge(u,v);
	}
	s=read(),t=read();
	bfs1(t);
	if(!vis[s]){
		printf("-1\n");
		return 0;
	}
	bfs2(s);
	bfs3(s);
	println(dis[t]);
	return 0;
}
2022/10/7 11:54
加载中...