题解 P2296 【寻找道路】

ww3113306 · 2017-10-28 23:10:19 · 题解

一遍AC，，本蒟蒻表示很开心

论如何找到可以走的点：

先从终点反向遍历一次，并把遍历到的点打个good标记；

如果起点没有good标记，就代表到不了起点，那么就输出-1

然后在循环找一遍所以的没有good标记的点，并对其直接相连的点打上can标记，即不能使用

最后就愉快的再一次BFS，一旦遍历到终点，就输出ans

#include<bits/stdc++.h>
using namespace std;
struct abc{
    int date,next;
};
int n,m,head[11000],headback[11000],ans[11000],tot,totback,s,t;
abc chain[201000],chainback[201000];
int q[11000];bool may[11000],good[11000],can[11000];
int read()
{
    char c;int x=0;
    c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();
    return x;
}
void add(int from,int want)//加边
{
    tot++;
    chain[tot].date=want;
    chain[tot].next=head[from];
    head[from]=tot;
}
void addback(int from,int want)//反向加边
{
    totback++;
    chainback[totback].date=want;
    chainback[totback].next=headback[from];
    headback[from]=totback;
} 
void first()//找出所有好点 
{
    int want,now,he=0,tail=1;
    q[1]=t;
    good[t]=true;
    while(he!=tail)
    {
        he++;
        want=headback[q[he]];
        now=chainback[want].date;
        while(now)//进行拓展
        {
            if(!good[now])//如果还没有被遍历过就加入队列
            {
                good[now]=true;
                q[++tail]=now;
            }
            want=chainback[want].next;
            now=chainback[want].date;
        }
    }
    if(!good[s])//如果到不了起点
    {
        printf("-1");
        exit(0);
    }
}
void second()
{
    int he=0,tail=1,i,now,want;
    memset(q,0,sizeof(q));
    q[1]=s;
    may[s]=true;
    while(he!=tail)
    {
        he++;
        want=head[q[he]];
        now=chain[want].date;
        while(now)
        {
            if(!good[now]||can[now])//如果这个点右边是坏的，或者本身就是坏的（貌似这个判断是多余的？因为与坏点相连的点根本进不来）
            {
                want=chain[want].next;
                now=chain[want].date;    
                continue;
            }
            if(!may[now])//如果没被访问过
            {
                may[now]=true;//标记已访问
                q[++tail]=now;//加入队列
                ans[now]=ans[q[he]]+1;//记录ans，由于BFS特性，直接+1即可
            }
            want=chain[want].next;
            now=chain[want].date;
        }
    }
}
void mid()//标记所有坏点 
{
    int now,want,i;
    for(i=1;i<=n;i++)
    {
        if(!good[i])//如果不是好点 
        {
            want=headback[i];
            now=chainback[want].date;
            while(now)
            {
                can[now]=true;//标记 
                want=chainback[want].next;
                now=chainback[want].date;
            }
        }
    } 
}
int main()
{
    int i,a,b;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        a=read();b=read();
        add(a,b);
        addback(b,a);//用于反向预处理 
    }
    scanf("%d%d",&s,&t);
    first();
    mid();
    second();
    printf("%d",ans[t]);//输出到t的最短距离
    return 0;
}