比赛 EYOI常规赛10th 评测结果 AAAAAAAAAA
题目名称 寻找道路 最终得分 100
用户昵称 ムラサメ 运行时间 0.131 s
代码语言 C++ 内存使用 2.04 MiB
提交时间 2023-03-29 18:16:32
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
bool inroad[10010],can[10010];
int dis[10010];
vector<int>side[10010];
vector<int>edis[10010];
int main(){
	freopen("roadb.in","r",stdin);
	freopen("roadb.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    int n,m,a,b,s,t;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        side[a].push_back(b);
        edis[b].push_back(a);
    }
    cin>>s>>t;
    can[t]=1;
    queue<int>que; 
    que.push(t);
    while(!que.empty()){
        int now=que.front();
        que.pop();
        for(int i=edis[now].size()-1;i>=0;i--){
            int to=edis[now][i];
            if(!can[to]){
                que.push(to);   
                can[to]=1;
            }
        }
    }
    if(!can[s]){
        cout<<"-1";
        return 0;
    }
    for(int i=1;i<=n;i++){
        if(can[i]){
            inroad[i]=1;
            for(int j=side[i].size()-1;j>=0;j--){
                int to=side[i][j];
                if(!can[to]){
                    inroad[i]=0;
                    break;
                }
            }
        }
    }
    if(!inroad[s]){
    	cout<<"-1";
    	return 0;
    }
    dis[s]=1;que.push(s);
    while(!que.empty()){
        int now=que.front();
        que.pop();
        if(now==t){
            cout<<dis[t]-1;
            return 0;
        }
        for(int i=side[now].size()-1;i>=0;i--){
            int to=side[now][i];
            if(inroad[to]&&!dis[to]){
                dis[to]=dis[now]+1;
                que.push(to);
            }
        }
    }
    cout<<"-1"<<endl;
}