P1613 跑路

题目

P1613 跑路

算法标签: 倍增, 动态规划, 最短路

思路

题目给定$2^k$步内都可以$1$秒到达, 因此可以定义一个状态$f[k][i][j]$表示是否存在一条长度为$2^k$的路径使得$i$能走到$j$, 观察数据范围, 点的数量是$50$, 可以直接枚举三个点, 计算出$f$数组, 如果能到达将两个点直接距离标记为$1$, 然后求最短路即可

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef unsigned long long ULL;
const int N = 60, M = 1e4 + 10, K = 65;

int n, m;
int f[K][N][N], d[N][N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    memset(d, 0x3f, sizeof d);
    for (int i = 1; i <= n; ++i) d[i][i] = 0;

    for (int i = 0; i < m; ++i) {
   
        int u, v;
        cin >> u >> v;
        d[u][v] = 1;
        f[0][u][v] = 1;
    }

    for (int k = 1; k < K; ++k) {
   
        for (int i = 1; i <= n; ++i) {
   
            for (int t = 1; t <= n; ++t) {
   
                for (int j = 1; j <= n; ++j) {
   
                  if (f[k - 1][i][t] && f[k - 1][t][j]) {
   
                      f[k][i][j] = 1;
                      d[i][j] = min(d[i][j], 1);
                  }
                }
            }
        }
    }

    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 ans = d[1][n];
    cout << ans << "\n";
    return 0;
}