题目描述

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

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

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

注意：图G 中可能存在重边和自环，题目保证终点没有出边。

请你输出符合条件的路径的长度。

思路

题目的意思是最短路上的点的所有出度都必须可以走到终点

首先从终点进行一次dfs，标记出那些点可以走到，然后spfa一下，每走一个点都暴力枚举全部出度，判断一下就可以了

#include <stdio.h>
#include <queue>
#include <iostream>
#define maxn 200001
#define INF 2147483647
using namespace std;
int l=0,s;
struct arr 
{ 
    int x,y,w,next;   
};
int x,y,z,e;
arr edge[maxn],edge1[maxn];
int ls[maxn],ls1[maxn];
int state[maxn];
bool exits[maxn];
int f[maxn],c[maxn],fl[maxn];
int dfs(int x)
{
    if (x==0) return 0;
    int i=ls1[x];
    while (i!=0)
    {   
        if(fl[edge1[i].y]==0)
        {
            f[edge1[i].y]=1;
            fl[edge1[i].y]=1;
            dfs(edge1[i].y);
        }
        i=edge1[i].next;
    }
    return 0;
}
int spfa()
{
    int i;
    queue <int> t;
    t.push(s);
    state[s]=0;
    exits[s]=true;
    do
    {
        int tt=t.front();
        t.pop();
        i=ls[tt];
        int j=ls[tt],ff=1;
        while (j!=0)
        {
            if (f[edge[j].y]==0) ff=0;
            j=edge[j].next;
        }
        while (i!=0&&ff==1) 
        {
            if (state[edge[i].x]+edge[i].w<state[edge[i].y]&&f[edge[i].y]>0&&f[edge[i].x]>0)
            {
                state[edge[i].y]=state[edge[i].x]+edge[i].w;
                if (exits[edge[i].y]==false)
                {
                    t.push(edge[i].y);
                    exits[edge[i].y]=true;
                }
            }
            i=edge[i].next;
        }
        exits[tt]=false;
    }
    while (!t.empty());
}
int main()
{
    int j,k,n,m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        edge[++l]=(arr){x,y,1,ls[x]};
        edge1[l]=(arr){y,x,1,ls1[y]};
        c[x]++;
        ls[x]=l;
        ls1[y]=l;
    }
    for (int i=1;i<maxn;i++)
        state[i]=INF;
    scanf("%d%d",&s,&e);
    fl[e]=1;
    f[e]=1;
    dfs(e);

    spfa();

    if (state[e]==INF) state[e]=-1;
    printf("%d\n",state[e]);
}