蒟蒻求调 玄关
查看原帖
蒟蒻求调 玄关
772368
Wind_love楼主2024/5/17 13:16

样例不过 but 20pts

#include<bits/stdc++.h>
#define int long long
using namespace std;
int head[200005],tot,d[200005],vis[200005];
struct node{
	int v,w,nxt;
}a[200005];
void add(int u,int v,int w){
	a[++tot].v=v;
	a[tot].w=w;
	a[tot].nxt=head[u];
	head[u]=tot;
}
priority_queue< pair<int,int> > q;
int n,m,s,t;
int v2[200005],sp[200005];
bool dfs(int x){
	if(x==t){
		sp[x]=1;
		return 1;
	}
	for(int i=head[x];i;i=a[i].nxt){
		int y=a[i].v;
		if(v2[y])continue;
		v2[y]=1;
		if(dfs(y))sp[x]=1;
	}
	//cout<<x<<":"<<sp[x]<<endl;
	return sp[x];
}
void dij(){
	memset(d,0x3f,sizeof d);
	memset(vis,0,sizeof vis);
	d[s]=0;
	q.push(make_pair(-d[s],s));
	while(!q.empty()){
		int x=q.top().second;q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(int i=head[x];i;i=a[i].nxt){
			int y=a[i].v,z=a[i].w;
			if(d[y]>d[x]+z&&sp[y]){
				d[y]=d[x]+z;
				//cout<<x<<"->"<<y<<":"<<d[y]<<endl;
				q.push(make_pair(-d[y],y));
			}
		}
	}
	return;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		add(u,v,1);
	}
	cin>>s>>t;
	for(int i=1;i<=n;i++){
		if(!v2[i])dfs(i);
	}
	dij();
	if(d[t]==0x3f3f3f3f){
		cout<<-1;
	}
	else{
		cout<<d[t];
	}
	return 0;
}
2024/5/17 13:16
加载中...