Luogu_P1613 跑路 题解

发现和最短路差不多，不过不能朴素的跑最短路。考虑对于每两个相隔 \(2\) 的整数次幂的点建边，在这个新图上跑最短路就是答案。设 \(f_{i,j,k}\) 表示从点 \(i\) 跳 \(2^k\) 步能否到点 \(j\)，转移方程就是一个普通的倍增。如果点 \(i\) 和点 \(j\) 可以一步到达，那么就在新图上建一条长度为 \(1\) 的边。跑 Floyd 最短路即可。

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

const int MAXN = 105;
int n, m, dis[MAXN][MAXN]; bool f[MAXN][MAXN][MAXN];

signed main(void) {
	cin >> n >> m;
	memset(dis, 0x3f, sizeof dis);
	for (int i = 1; i <= m; ++i) {
		int x, y;
		cin >> x >> y;
		dis[x][y] = f[x][y][0] = 1;
	}
	for (int k = 1; k < 105; ++k) {
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				for (int l = 1; l <= n; ++l) {
					if (f[j][i][k - 1] && f[i][l][k - 1]) {
						dis[j][l] = f[j][l][k] = 1;
					}
				}
			}
		}
	}
	for (int k = 1; k <= n; ++k) {
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (dis[i][j] > dis[i][k] + dis[k][j]) {
					dis[i][j] = dis[i][k] + dis[k][j];
				}
			}
		}
	}
	cout << dis[1][n] << endl;
	return 0;
}