洛谷P1613 跑路

很巧妙的一道题

设$f\left [ i \right ]\left [ u \right ]\left [ v \right ]$为u 到v 之间是否存在长度为$2^{i}$的路

$$f\left [ i \right ]\left [ u \right ]\left [ v \right ]=f\left [ i -1\right ]\left [ u \right ]\left [ k \right ]\ and \ f\left [ i -1\right ]\left [ k \right ]\left [ v \right ]$$

设$d\left [ u\right ]\left [v \right ]$为u 到v 需要的时间

$$\exists f\left [ i \right ]\left [ u \right ]\left [ v \right ]=1,d\left [ u\right ]\left [v \right ]=1$$

最后跑一遍Floyd 即可

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=55,INF=1<<25;
int n,m,d[N][N],f[N][N][N];
inline int read()
{
    register int x=0,t=1;
    register char ch=getchar();
    while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if (ch=='-') t=-1,ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*t;
}
void Floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++) 
            for(int j=1;j<=n;j++) 
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        f[0][u][v]=1;
    }
    for(int i=1;i<N;i++)
        for(int u=1;u<=n;u++)
            for(int v=1;v<=n;v++) 
                for(int k=1;k<=n;k++) 
                    if (f[i-1][u][k]&&f[i-1][k][v]) f[i][u][v]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) d[i][j]=INF;
    for(int i=0;i<N;i++)
        for(int u=1;u<=n;u++)
            for(int v=1;v<=n;v++) 
                if (f[i][u][v]) d[u][v]=f[i][u][v];
    Floyd();
    printf("%d\n",d[1][n]);
    return 0;
}