题解 P2296 【寻找道路】

「QQ红包」 · 2016-11-09 21:42:37 · 题解

将所有边倒过来来从终点往回搜看能否搜到。

然后从起点开始广搜，入队前先判断它所连的点是否能到达终点。

边集数组比vector快……

具体见代码

#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
int n,m;//n个点m条边
int e[200010],ee[200010];
int u[200010],v[200010];//边集数组 
int uu[200010],vv[200010];//边集数组 
int d[10010],dd[10010];//最后一个点位置。 
int ff[10010];//标记是否可到达终点 
int f[10010];//标记是否搜过。 
struct he
{
    int n;//编号
    int s;//距离 
}q[10010];
int s,t;//起点终点
int xx,yy,i,j; 
int mmin,l,r;
void dfs(int i)
{
    int j=i;
    while (j!=-1)
    {
        if (ff[vv[j]]==0)//没搜过 
        {
            ff[vv[j]]=1;//标记可以到达 
            dfs(dd[vv[j]]);//往下灌水 
        } 
        j=ee[j];
    }
} 
int main()
{
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)//初始化 
    {
        d[i]=-1;
        dd[i]=-1; 
    }
    for (i=1;i<=m;i++)
    {
        scanf("%d%d",&u[i],&v[i]);
        e[i]=d[u[i]];//存上一条边的位置 
        d[u[i]]=i; 

        uu[i]=v[i];vv[i]=u[i];//反过来。
        ee[i]=dd[v[i]];//存上一条边的位置 
        dd[v[i]]=i;
    }
    scanf("%d%d",&s,&t);
    ff[t]=1;
    dfs(dd[t]); 
    //for (i=1;i<=n;i++) cout<<ff[i]<<endl;
    if (ff[s]!=1)//起点无法到达终点 
    {
        printf("-1\n");
        return 0;
    }
    q[1].n=s;
    q[1].s=0;//起点入队
    l=0;
    r=1;
    mmin=-1;//初始化 
    f[s]=1;     
    while (l!=r)
    {
        l++;//队首出队
        if (q[l].n==t)//找到了点t 
        {
            if (mmin==-1) mmin=q[l].s;//找min 
            mmin=min(mmin,q[l].s);
            continue;
        }
        i=d[q[l].n];//搜i连的所有边 
        while (i!=-1)
        {
            j=d[v[i]];
            int f3=0;//标记用 
            while (j!=-1)//看与点v[i]相连的点是否都能到达终点，若都能，v[i]入队 
            {
                if (ff[v[j]]!=1)
                {
                    f3=1;//标记 
                }
                j=e[j];
            } 
            if (f3==1)//点v[i]有点不能到达终点 
            {
                i=e[i];
                continue;
            }
            if (ff[v[i]]==1&&f[v[i]]!=1)//可以到达终点,且没搜过。 
            {
                f[v[i]]=1;//标记
                r++;//入队
                q[r].n=v[i];
                q[r].s=q[l].s+1; 
            }
            i=e[i];
        }
    } 
    cout<<mmin;//输出 
    return 0;
}