随机真题赛第三轮(xhy&lfy讲题)

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0') f^=(c=='-'),c=getchar();
    while(c>'/') x=(x<<3)+(x<<1)+(c^'0'),c=getchar();
    return f?x:-x;
}
vector<int>e1[10010],e2[10010];  
int bo[10010],vs[10010];
int main(){
    n=read();m=read();
    for(int i=1;i<=m;i++){
     int u=read(),v=read();
     e1[u].push_back(v);
     e2[v].push_back(u);    
    }
    queue<int> q1; 
    s=read();
    t=read();
    bo[t]=1;
    q1.push(t);
    while(!q1.empty()){
        int no=q1.front();
        q1.pop();
        for(int i=0;i<e2[no].size();i++){
            int to=e2[no][i];
            if(!bo[to]){
                q1.push(t);
                bo[to]=1;
            }
        }
    }
    if(!bo[s]){
        puts("-1");
        return 0;
    }
    queue<int> q2; 
    vs[s]=1;
    q2.push(s);
    while(!q2.empty()){
        int no=q2.front();
        q2.pop();
        for(int i=0;i<e1[no].size();i++){
            int to=e1[no][i];
            if(bo[to]&&!vs[to]){
                q2.push(t);
                vs[to]=vs[no]+1;
            }
        }
    }
    printf("%d\n",vs[t]-1);
    return 0;
}

2 条评论

  • 1