美文网首页
题解 NOIP 2014 寻找道路

题解 NOIP 2014 寻找道路

作者: Ricardo_Y_Li | 来源:发表于2017-07-11 15:43 被阅读0次

    NOIP 2014 寻找道路

    题目描述 Description

    在有向图G中,每条边的长度均为1,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件:
    1.路径上的所有点的出边所指向的点都直接或间接与终点连通。
    2.在满足条件1的情况下使路径最短。
    注意:图G中可能存在重边和自环,题目保证终点没有出边。
    请你输出符合条件的路径的长度。

    输入描述 Input Description

    第一行有两个用一个空格隔开的整数n和m,表示图有n个点和m条边。
    接下来的m行每行2个整数x、y,之间用一个空格隔开,表示有一条边从点x指向点y。
    最后一行有两个用一个空格隔开的整数s、t,表示起点为s,终点为t。

    输出描述 Output Description

    输出文件名为road.out。
    输出只有一行,包含一个整数,表示满足题目描述的最短路径的长度。如果这样的路径不存在,输出-1。

    样例输入输出

    【样例输入#1】 Sample Input#1

    3 2
    1 2
    2 1
    1 3

    【样例输出#1】 Sample Output#1

    -1

    【样例输入#2】 Sample Input#2

    6 6
    1 2
    1 3
    2 6
    2 5
    4 5
    3 4
    1 5

    【样例输出#2】 Sample Output#2

    3

    样例输入输出说明

    【解释1】


    如上图所示,箭头表示有向道路,圆点表示城市。起点1与终点3不连通,所以满足题
    目᧿述的路径不存在,故输出- 1 。

    【解释2】

    Mou icon

    如上图所示,满足条件的路径为1 - >3- >4- >5。注意点2不能在答案路径中,因为点2连了一条边到点6,而点6不与终点5连通。

    图转自洛谷

    数据范围及提示 Data Size & Hint

    对于30%的数据,0< n ≤10,0< m ≤20;
    对于60%的数据,0< n ≤100,0< m ≤2000;
    对于100%的数据,0< n ≤10,000,0< m ≤200,000,0< x,y,s,t≤n,x≠t。

    题解

    我一开始拿到这道题的时候就认为这题不是一道bfs模板题吗,但后来发现要满足规则一并不是单纯的bfs模板跑一遍能解决的,所以我想到先从终点反向跑一遍bfs将能到达的点进行标记,然后再正向跑bfs,只遍历标记过的点即可
    代码如下

    C++代码

    /*
        Name: Find the Way
        Copyright: Ricardo_Y_Li
        Author: Ricardo_Y_Li
        Date: 11/07/17 15:37
        Description: NULL
    */
    
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    #include<queue> 
    using namespace std;
    
    vector<int>map_z[10010],map_f[10010];
    //定义正向图与反向图 
    queue<int>q;
    bool vis_z[10010],vis_f[10010];//正向标记与反向标记 
    int dis[10010];//dis[i]表示点i到起点的距离 
    int n,m,s,e;
    
    bool check(int x){//检查点x是否符合规则一 
        int len=map_z[x].size()-1;
        for(int i=0;i<=len;i++){
            int v=map_z[x][i];
            if(!vis_f[v])//若没标记则返回0 
                return 0;
        }
        return 1;
    }
    
    void bfs_z(){//正向bfs找最短路 
        while(!q.empty())//清空队列 
            q.pop();
        q.push(s);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            int len=map_z[u].size()-1;
            if(!check(u))
                continue;
            for(int i=0;i<=len;i++){
                int v=map_z[u][i];
                if(!vis_z[v]){
                    vis_z[v]=1;
                    dis[v]=dis[u]+1;
                    q.push(v);
                }
                if(v==e){//找到终点直接返回 
                    return;
                }
            }
        }
        
    }
    
    void bfs_f(){//反向bfs进行标记 
        while(!q.empty())//清空队列 
            q.pop();
        q.push(e);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            int len=map_f[u].size()-1;
            for(int i=0;i<=len;i++){
                int v=map_f[u][i];
                if(!vis_f[v]){
                    vis_f[v]=1;
                    q.push(v);
                }
            }
        }
        return;
    }
    
    int main(){
        ios::sync_with_stdio(false);
        memset(vis_z,0,sizeof(vis_z));
        memset(vis_f,0,sizeof(vis_f));
        memset(dis,-1,sizeof(dis));
        //把距离都初始化成-1,若无法到达就直接输出-1了 
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            map_z[x].push_back(y);
            map_f[y].push_back(x);
        }
        cin>>s>>e;
        dis[s]=0;//起点到自己的距离肯定为0 
        vis_f[e]=1;//反向标记时先把终点自己标记上 
        bfs_f();
        bfs_z();
        cout<<dis[e];
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:题解 NOIP 2014 寻找道路

          本文链接:https://www.haomeiwen.com/subject/jykmhxtx.html