洛谷1613 跑路

题意

要从一个 $N$ 点 $M$ 边的有向图的 $1\rightarrow N$ ，每秒可以走 $2^k$ 条边（$k$ 是任意自然数），求最少要花多少秒。

$N\le 50 \ , \ M\le 10000$ 。

题解

用一个 bool 数组 $s[i][j][p]$ 表示能否走 $2^p$ 条边从 $i\rightarrow j$ ，可以通过倍增预处理出所有情况。这样就得到了所有能在 $1s$ 内到达的边。

然后把上述的边重新连成一个新图，用 $\text{Floyd}$ 跑最短路即可。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

bool s[55][55][32];
int n,m,a,b,dis[55][55];

signed main()
{
    n=read(); m=read();
    memset(dis,0x3f,sizeof(dis));
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read();
        s[a][b][0]=1;
        dis[a][b]=1;
    }
    for (int p=0;p<32;p++)
    {
        for (int k=1;k<=n;k++)
        {
            for (int i=1;i<=n;i++)
            {
                for (int j=1;j<=n;j++)
                {
                    if (!s[i][k][p] || !s[k][j][p]) continue;
                    s[i][j][p+1]=1;
                    dis[i][j]=1;
                }
            }
        }
    }
    for (int k=1;k<=n;k++)
    {
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=n;j++)
            {
                if (dis[i][k]+dis[k][j]>=dis[i][j]) continue;
                dis[i][j]=dis[i][k]+dis[k][j];
            }
        }
    }
    return !printf("%d",dis[1][n]);
}