[JZOJ3155]「提高A组模拟」『BFS』最短路

题解 BFS

题目

$N$ 个结点、$M$ 个含$K$ 个结点的完全子图构成一个奇怪的图，问从结点$1$走到结点$N$最少需要经过多少个结点。

$1\le N \le 10^6,1\le K \le 10^3,1\le M\le 10^3$

题解

考虑缩点，将完全子图看成一个点，然后连上完全子图内的点。可以减少边的数量，从而来跑BFS，注意最后的答案是$\dfrac{\text{ans}}{2}+1$

Code

#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
    int to,next;
}a[2000005];
int n,k,m,x,tot,h,t;
int b[200005],d[101005][3],head[101005];
void add(int x,int y)
{
    a[++tot].to=y;
    a[tot].next=head[x];
    head[x]=tot;
}
int main()
{
    scanf("%d%d%d",&n,&k,&m);
    for (int i=1;i<=m;++i)
    {
        for (int j=1;j<=k;++j)
            scanf("%d",&x),add(x,n+i),add(n+i,x);
    }
    h=0;t=1;
    d[1][1]=1;d[1][2]=1;
    b[1]=true;
    while (h<t)
    {
        int u=d[++h][1];
        for (int i=head[u];i;i=a[i].next)
        {
            int v=a[i].to;
            if (!b[v])
            {
                b[v]=true;
                d[++t][1]=v;
                d[t][2]=d[h][2]+1;
                if (v==n)
                {
                    printf("%d\n",d[t][2]/2+1);
                    return 0;
                }
            }
        }
    }
    printf("-1\n");
    return 0;
}