洛谷题单指南-树与图上的动态规划-P1613 跑路

原题链接：https://www.luogu.com.cn/problem/P1613

题意解读：求从1到n的路径最少包含多少个2^k。

解题思路：

如果对于从所有点经过2^k的路径能到达的点，都标记为可达且距离为1

那么从1到n最少包含多少个2^k，就是一个求最短路径的问题，数据量不大，可以用Floyd算法

而对于标记两点是否可达，可以借助倍增ST表的思想：

设f[i][j][k]=1表示从i到j路径长度是2^k，那么对于所有的k，所有的中间节点t，有f[i][j][k] = f[i][t][k-1] && f[t][j][k-1]

同时设g[i][j]表示从i到j最少走几秒，在更新f时同步更新g，最后对g跑一遍Floyd即可。

100分代码：

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

const int N = 55;
bool f[N][N][64]; //f[i][j][k]=1表示从i到j路径长度是2^k
int g[N][N]; //g[i][j]表示从i到j最少走几秒

int n, m;

int main()
{
    memset(g, 0x3f, sizeof(g));
    cin >> n >> m;
    while(m--)
    {
        int u, v;
        cin >> u >> v;
        f[u][v][0] = 1;
        g[u][v] = 1;
    }

    //倍增预处理
    for(int k = 1; k < 64; k++)
        for(int t = 1; t <= n; t++)
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    if(f[i][t][k - 1] && f[t][j][k - 1])
                        f[i][j][k] = 1, g[i][j] = 1;

    //Floyd
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

    cout << g[1][n];
    return 0;
}