题解 P2296 【寻找道路】

核弹头AC · 2018-04-01 18:47:06 · 题解

有人问我，这题用普通的二维数组要爆呀，内存不够呀· · ·

甚至有人提交出现了MLE（不多见！）

于是，我回复：vector不就行啦？？？

千万人

恍然大悟· · ·

#include <cstdio>
#include <vector>
using namespace std;
int n,m,started,ended;
int arr[10001]={0};
int que[10001],head,tail,step[10001],book[10001];
vector <int> e[10001],re[10001];
void dfs(int u)
{
    if(arr[u]==1) return;
    arr[u]=1;
    for(int i=0;i<re[u].size();i++)
    {
        dfs(re[u][i]);
    }
    return ;
}
int main()
{
    int u,v;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&u,&v);
        e[u].push_back(v);
        re[v].push_back(u);
    }
    scanf("%d %d",&started,&ended);
    dfs(ended);
    for(int i=1;i<=n;i++)
    {
        if(arr[i]==1)
        {
            for(int j=0;j<e[i].size();j++)
            {
                v=e[i][j];
                if(arr[v]==0)
                {
                    arr[i]=-1;
                }
            }
        }
    }
    head=1;
    tail=1;
    que[tail]=started;
    step[tail]=0;
    tail++;
    int flag=0;
    while(head<tail)
    {
        u=que[head];
        for(int i=0;i<e[u].size();i++)
        {
            v=e[u][i];
            if(book[v]==0 && arr[v]==1)
            {
                book[v]=1;
                que[tail]=v;
                step[tail]=step[head]+1;
                tail++;
            }
            if(v==ended)
            {
                flag=1;
                break;
            }
        }
        if(flag==1)
        {
            break;
        }
        head++;
    }
    if(head<tail)
    {
        printf("%d",step[tail-1]);
    }
    else
    {
        printf("-1");
    }
    return 0;
}