欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷P2296-寻找道路【日常图论,最短路,SPFA】

程序员文章站 2022-07-13 11:58:51
...

题目

一个有向图,要求满足要求的最短路径,要求为:

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

输入1

3 2 (3个点,2条边)
1 2 (1和2之间可以连接)
2 1
1 3 (从1到3)

输出1

-1
洛谷P2296-寻找道路【日常图论,最短路,SPFA】

输入2

6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5

输出2

3
洛谷P2296-寻找道路【日常图论,最短路,SPFA】


解题思路

其实我们就求出满足要求的点,然后在这些点里找最短路,还有本人这里的方法比较复杂和麻烦


代码

#include<cstdio>
using namespace std;
struct woc{
    int next,x,y;
};//日常邻接表
woc a[200001],lt[200001];
int xx,yy,n,m,k,state[10001],ls[10001],t,head,tail,f[10001],star,over;
int fls[10001];
bool ltfl[10001];
bool v[10001];
void check()//求所有可以直接或间接到终点的边
{
    int t=0;
    int head=0;
    int tail=1;
    state[1]=over;
    ltfl[state[1]]=true;//初始化
    while (head!=tail)
    {
        head++;
        head=(head-1)%n+1;
        t=fls[state[head]];//求边
        while (t!=0)
        {
            if (!ltfl[lt[t].y])
            {
                tail++;
                tail=(tail-1)%n+1;
                state[tail]=lt[t].y;
                ltfl[lt[t].y]=true;//标记
            }
            t=lt[t].next;//求下一条边
        }
    }
}
bool ok(int x)//是否满足要求
{
    int t=ls[x];
    while (t!=0)
    {
        if (!ltfl[a[t].y]) return false;
        t=a[t].next;
    }
    return true;
}
int main()
{
    scanf("%d%d",&n,&m);
    state[1]=1;
    int u=0;    
    for (int i=1;i<=m;i++)
    {
        scanf("%d",&xx);
        scanf("%d",&yy);
        a[++u].next=ls[xx];
        ls[xx]=u;
        a[u].x=xx;
        a[u].y=yy;//边
        lt[u].next=fls[yy];
        fls[yy]=u;
        lt[u].y=xx;
        lt[u].x=yy;//记录一条回去的边
    }   
    scanf("%d%d",&star,&over);
    for (int i=1;i<=n;i++) f[i]=2147483647;//初始化    
    check();//求所有可以直接或间接到终点的边
    head=0;
    tail=1;
    state[1]=star;
    v[state[1]]=true;
    f[star]=0;//初始化×2
    while (head!=tail)
    {
        head++;//出队
        head=(head-1)%n+1;//循环队列
        t=ls[state[head]];
        while (t!=0)
        {
            if (f[a[t].x]+1<f[a[t].y] && ok(a[t].y))//判断是否满足要求
            {
                f[a[t].y]=f[a[t].x]+1;//松弛
                if (!v[a[t].y])
                {
                    tail++;//入队
                    tail=(tail-1)%n+1;//循环队列
                    state[tail]=a[t].y;
                    v[a[t].y]=true;
                }
            }
            t=a[t].next;//下一条边
        }
        v[state[head]]=false;//解封
    }
    if (f[over]==2147483647) printf("-1");//是否有解
    else printf("%d\n",f[over]);
}