[题解]LuoGu1613：跑路

原题传送门

倍增法

说说我自己对倍增法的理解吧 这应该是一个思想，用来加速个体的信息合并

单个的个体，两个相同长度的区间的信息合并到一起，时间通常是$O(logn)$

然后，倍增法应该得满足要求：信息可合并

就没了

---

本题，n<=50，肯定$floyd$ 所以我们需要知道那些点可以一步走到，接下来就是folyd的事情了

如何预处理是个问题，但是题目中机器的特点提醒我们可以用倍增 $f[i][j][l]=1$表示点i到点j有一条长度为$2^l$的路径 这个可以用倍增预处理出来 而$w[i][j]表示i->j最短路$，又当$w[i][j]=1$需要满足存在$l$，使得$f[i][j][l]=1$

Code：

#include <bits/stdc++.h> #define maxn 110 using namespace std; int w[maxn][maxn], f[maxn][maxn][maxn], n, m; inline int read(){ int s = 0, w = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') w = -1; for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48); return s * w; } int main(){ n = read(), m = read(); memset(w, 0x3f3f3f3f, sizeof(w)); for (int i = 1; i <= m; ++i){ int x = read(), y = read(); f[x][y][0] = 1, w[x][y] = 1; } for (int l = 0; l <= 31; ++l) for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if (f[i][k][l] && f[k][j][l]) f[i][j][l + 1] = 1, w[i][j] = 1; for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) w[i][j] = min(w[i][j], w[i][k] + w[k][j]); printf("%d\n", w[1][n]); return 0; }