求助,差Subtask #1没a
查看原帖
求助,差Subtask #1没a
839638
linjianju_xi楼主2024/3/30 09:11

代码:

#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

我的代码记录

2024/3/30 09:11
加载中...