NOIP2014 寻找道路

2018-10-16 16:28:38


题目大意:

在有向图G 中,每条边的长度均为1 ,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件:

1 .路径上的所有点的出边所指向的点都直接或间接与终点连通。

2 .在满足条件1 的情况下使路径最短。

Solution

首先,预处理,把每条边反向。

从终点开始bfs,标记从终点开始可以走到的点。

第二步,枚举每一个点,如果这个点没有被标记,则枚举它的每一条出边(反向后的),如果它指向的点被标记,则说明这个被标记的点不合法,删除。

第三步,在合法点上bfs,单源最短路。找到答案

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct edg{
    int next,to;
}edge[200001];
edg hhhh[200001];
int head[200001],hed[200001];
int cnt,qwq;
int sec_ve[200001];
int ve[20001];
int vis[20001],dis[20001];
void add(int a,int b)
{
    edge[++cnt].to=b;
    edge[cnt].next=head[a];
    head[a]=cnt;
    hhhh[cnt].to=a;
    hhhh[cnt].next=hed[b];
    hed[b]=cnt;
}
int s,t;
int x,y;
queue<int>q;
queue<int>k;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)dis[i]=9999;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        if(x!=y)add(x,y);
    }
    scanf("%d%d",&s,&t); 
    k.push(t);
    ve[t]=1;
    while(!k.empty())
    {
        int u=k.front();
        k.pop();
        for(int i=hed[u];i;i=hhhh[i].next)
        {
            int v=hhhh[i].to;
            if(!ve[v]){
               ve[v]=1;
                    k.push(v);
            }
        }
    }
    for(int i=1;i<=n;i++)if(!ve[i])
        for(int e=hed[i];e;e=hhhh[e].next)
            sec_ve[hhhh[e].to]=true;
    for(int i=1;i<=n;i++)vis[i]=0;
    dis[s]=0;
    q.push(s);
    vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        if(!ve[u]||sec_ve[u])continue;
        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(dis[v]>dis[u]+1){
                dis[v]=1+dis[u];
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
        if(dis[t]<9999)printf("%d",dis[t]);
        else printf("-1");
}