代码:
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define fo(i,a,b) for(int i=(a);i<(b);++i)
#define PII pair<int,int>
#define LL long long
using namespace std;
const int N=1e4+5;
int n,m;
vector<int> G[N],G2[N];
int vis[N];
int S,T;
bool ke[N];
void bfs2(){
queue<int> q;q.push(T);
vis[T]=1;
while(q.size()){
int u=q.front();q.pop();
for(auto &v:G2[u]){
if(vis[v]==1) continue;
q.push(v);vis[v]=1;
}
}
}
int bfs(){
memset(vis,0,sizeof vis);
queue<PII> q;
q.push({S,0});vis[S]=1;
while(!q.empty()){
PII u=q.front();q.pop();
if(u.first==T) return u.second;
for(auto v:G[u.first]) if(ke[v]==true) {
if(vis[v]) continue;
q.push({v,u.second+1});
vis[v]=1;
}
}
return -1;
}
int main(){
std::ios::sync_with_stdio(0);
cin>>n>>m;
rep(i,1,m){
int x,y;
cin>>x>>y;
G[x].push_back(y);
G2[y].push_back(x);
}
cin>>S>>T;
bfs2();
rep(u,1,n){
bool flag=true;
for(auto &v:G[u]){
if(vis[v]==0){
flag=false;
break;
}
}
ke[u]=flag;
}
cout<<bfs();
}
输入:
4 6
4 2
4 4
1 1
1 4
1 1
1 3
1 3
我的输出:
-1
题解代码输出:
-1