1 条题解

  • 1
    @ 2022-7-20 21:55:35
    #include<iostream>
    #include<vector>
    #include<cstdio>
    #include<algorithm>
    #include<queue>
    using namespace std;
    bool inroad[10010],can[10010];       //inroad 表示此点是否可以出现在路径上  can 表示此点是否可以到达终点 
    int dis[10010];                      //dis 表示此点距离起点的距离 
    vector<int>side[10010];              //正向建边 
    vector<int>edis[10010];              //反向建边 
    int main()
    {
        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;                        //终点先设置为 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])			            //这里需要特殊判定一下起点是否满足条件,感谢 @WestTree 的HACK		
        {
        	cout<<"-1";
        	return 0;
            }
        dis[s]=1;que.push(s);
        while(!que.empty())                 //从起点bfs,只经过①点,找出最短距离 
        {
            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";                     //否则还是无法到达 
    }
    
    • 1

    信息

    ID
    1248
    时间
    1000ms
    内存
    125MiB
    难度
    4
    标签
    递交数
    2
    已通过
    2
    上传者