20pts 全部输出-1
查看原帖
20pts 全部输出-1
482660
konyakest楼主2022/10/6 12:09

rt

wa的点全都是有解但输出了-1

#include <bits/stdc++.h>
using namespace std;
#define F(i,j,k) for (signed i=signed(j);i<=signed(k);i++)
#define endl '\n'
const int maxn=1e4+5;

int n,m,x,y,s,t;
vector<int> v[maxn],v2[maxn];
set<pair<int,int>> st;
bool vis[maxn],lt[maxn],isd[maxn];
void dfs(int x){
	if(x==t) {lt[x]=1;return;}
	if(vis[x]) return;
	vis[x]=1;
	for(auto i:v[x]) dfs(i),lt[x]|=lt[i];
}
void dfs2(int x){
	if(x==t) {isd[x]=1;return;}
	if(vis[x]) return;
	vis[x]=1;
	bool f=1;
	for(auto i:v[x]) if(!lt[i]) f=0;
	if(f) isd[x]=1;
	for(auto i:v[x]) dfs2(i);
}
void dfs3(int x,int cnt){
	// cerr<<x<<" "<<cnt<<endl;
	if(x==t){
		cout<<cnt;
		exit(0);
	}
	if(vis[x]) return;
	vis[x]=1;
	for(auto i:v2[x]) dfs3(i,cnt+1);
}

signed main() { 
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	F(i,1,m) {
		cin>>x>>y;
		if(x==y||st.count({x,y})) continue;
		v[x].push_back(y);
		st.insert({x,y});
	}
	cin>>s>>t;
	dfs(s);
	memset(vis,0,sizeof vis);
	F(i,1,n) cerr<<lt[i]<<" ";
	dfs2(s);
	F(i,1,n){
		if(!isd[i]) continue;
		for(auto j:v[i]) if(isd[j]) v2[i].push_back(j);
	}
	memset(vis,0,sizeof vis);
	dfs3(s,0);
	cout<<-1;
	return 0; 
}






2022/10/6 12:09
加载中...