跑路

标签（空格分隔）： 倍增 Floyd

---

题目描述

戳这里

题解

这道题如果路径是$2^k$则花费为1，我们可以利用这个性质用Floyd的思想把路径长度为$2^k$的点对处理出来，$dis[i][j][k]$表示$i$到$j$存在一条长度为$2^k$的路径。
这个处理出来以后，我们设$f[i][j]$表示$i$到$j$的最小花费，若原来$dis[i][j][k]$存在,则$f[i][j]=1$，否则$f[i][j]=INF$
然后对$f$跑一次Folyd即可

代码

#include<bits/stdc++.h>
#define N 60
using namespace std;

int n, m, u, v;
bool d[N][N][N];
int f[N][N];

int main()
{
    memset(d, false, sizeof(d));
    memset(f, 0x3f3f3f3f, sizeof(f));
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i ++)
    {
        scanf("%d%d", &u, &v);
        d[u][v][0] = true;
    }
    for(int b = 1; b <= 32; b ++)
        for(int k = 1; k <= n; k ++)
            for(int i = 1; i <= n; i ++)
                for(int j = 1; j <= n; j ++)
                    if(d[i][k][b - 1] && d[k][j][b - 1])
                        d[i][j][b] = true;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            for(int b = 0; b <= 32; b ++)
                if(d[i][j][b]) f[i][j] = 1;// printf("%d %d %d", i, j, b), system("pause");
    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
    printf("%d", f[1][n]);
    return 0;
}