题解 P2296 【寻找道路】

曹老师 · 2018-10-22 11:07:23 · 题解

我没有其他题解里面的大佬们厉害，所以用了最朴素的方法……貌似可以被hack，不信你试试（逃

1.输入的时候建两张图，正图和反图（待会用得上）

2.bfs一遍反图，求出终点能到达的点，打上vis标记

3.根据题目中的条件，枚举每一个点，判断与该点连接的点是否都可以被终点访问

4.如果不满足3中的条件，打上del标记

5.最短路dij一遍，注意在压入队列的时候判断一下del标记

提醒自己也提醒你：如果你是重载的话，不等号千万不要写错。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<set>
#define INF 2147483647
using namespace std;
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int _read(){ char ch=nc();int sum=0; while(!(ch>='0'&&ch<='9'))ch=nc(); while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc(); return sum; }
template<typename __Type_of_print>
void print(__Type_of_print x)
{ if(x<0){putchar('-');x=-x;} if(x>9)print(x/10); putchar(x%10+'0'); }

struct Node {
    int to , next;
};
Node e[200005] , z[200005];
struct Que {
    int num , len;
    bool operator < (const Que &a) const {
        return a.len < len;
    }
    Que(int nn , int dd) {
        num = nn , len = dd;
    }
};
int n , m , head[10005] , tot , s , t , ans , del[10005] , dis[10005] , vis[10005] , headz[10005] , totz;
inline int mymax(int a , int b) { return a>b?a:b; }

inline void add(int x , int y) {
    tot++;
    e[tot].next = head[x];
    e[tot].to = y;
    head[x] = tot;
}

inline void addz(int x , int y) {
    totz++;
    z[totz].next = headz[x];
    z[totz].to = y;
    headz[x] = totz;
}

inline void bfs(int x) {
    queue<int>q;
    q.push(x);
    vis[x] = 1;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i=head[u]; i; i=e[i].next) {
            int v = e[i].to;
            if(vis[v])
                continue;
            q.push(v);
            vis[v] = 1;
        }
    }
}

inline void dij(int s) {
    priority_queue<Que>q;
    for(int i=1; i<=n; i++)
        dis[i] = INF;
    dis[s] = 0;
    q.push(Que(s,dis[s]));
    while(!q.empty()) {
        Que u = q.top();
        q.pop();
        if(dis[u.num] != u.len)
            continue;
        for(int i=headz[u.num]; i; i=z[i].next) {
            int v = z[i].to;
            if(del[v])
                continue;
            if(dis[v] > dis[u.num] + 1) {
                dis[v] = dis[u.num] + 1;
                q.push(Que(v , dis[v]));
            }
        }
    }
}

int main() {
    n = _read() , m = _read();
    for(int i=1; i<=m; i++) {
        int x , y;
        x = _read() , y = _read();
        add(y , x); addz(x , y);
    }
    s = _read();
    t = _read();
    bfs(t);
    for(int i=1; i<=n; i++) {
        int flag = 0;
        for(int j=headz[i]; j; j=z[j].next) {
            int v = z[j].to;
            if(!vis[v]) {
                flag = 1;
                break;
            }
        }
        if(flag)
            del[i] = 1;
    }
    dij(s);
    if(dis[t]==INF)
        dis[t] = -1;
    print(dis[t]);
    return 0;
}