题解 P2296 【寻找道路】

Nepenthe · 2017-10-01 10:39:49 · 题解

看到2条件我们知道这题是求书上最短路

所以我们考虑怎么满足条件1

我们自然的想到，对于每个点搜索判断是否可以到终点

然而似乎很复杂。。

逆向思维 我们这么考虑，如果我们不能正着判断，那我们就逆向判断，从终点开始bfs判断哪些点可以到终点，复杂程度就大大降低了。

有点想我们走迷宫，若是从起点走卡住了，就从终点开始走。。

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#define siz 10001
using namespace std;
int n,m,s,t,pos,rpos;
int first[siz],rfirst[siz];
bool hav[siz][siz],reach[siz],vis[siz];
struct Node {
    int nx,num;
} node[siz*20],rnode[siz*20];
inline void ins(int u,int v) { // 
    node[++pos].num=v;
    node[pos].nx=first[u];
    first[u]=pos;
}
inline void rins(int u,int v) { // 
    rnode[++rpos].num=v;
    rnode[rpos].nx=rfirst[u];
    rfirst[u]=rpos;
}
void bfs() {    // 
    int line[siz],head=1,tail=1;
    line[1]=t; vis[t]=1;
    while(head<=tail) {
        for(int i=rfirst[line[head]]; i; i=rnode[i].nx)
            if(!vis[rnode[i].num]) {
                reach[rnode[i].num]    =1;
                vis[rnode[i].num]=1;
                line[++tail]=rnode[i].num;
            }
        head++;
    }
}
void answer() {
    int line[siz][2],head=1,tail=1,pd=0;
    line[1][0]=s; vis[s]=1;
    while(head<=tail) {
        for(int i=first[line[head][0]]; i; i=node[i].nx)
            if(!vis[node[i].num]) {
                vis[node[i].num]=1;
                line[++tail][0]=node[i].num;
                line[tail][1]=line[head][1]+1;
                if(line[tail][0]==t) {
                    printf("%d",line[tail][1]);
                    pd=1;
                    break;
                }
            }
        head++;
    }
    if(!pd) puts("-1");
}
int main() {
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++) {
        scanf("%d%d",&s,&t);
        if(s!=t&&!hav[s][t]&&!hav[t][s]) {  
            ins(s,t);
            rins(t,s);
            hav[s][t]=hav[t][s]=1;
        }
    }
    scanf("%d%d",&s,&t);
    bfs(); reach[t]=1;
    if(!reach[s]) {
        puts("-1");
        return 0;
    }
    memset(vis,0,sizeof(vis));
    for(int i=1; i<=n; i++)
        if(!reach[i]) vis[i]=1;
        else for(int j=first[i]; j; j=node[j].nx)
                if(!reach[node[j].num]) {
                    vis[i]=1;
                    break;
                }
    answer();
    return 0;
}