题目链接:P1613 跑路
题意
给定包含 $n$ 个点和 $m$ 条边的有向图,每条边的长度为 $1$ 千米。每秒钟可以跑 $2^k$ 千米,问从点 $1$ 到点 $n$ 最少需几秒。
思路
倍增 DP Floyd
令 $dp[i][j][k]$ 表示从 $i$ 到 $j$ 是否存在长度为 $2^k$ 的路径。
那么如果 $dp[i][t][k - 1]$ 和 $dp[t][j][k - 1]$ 都为 $1$ 则 $dp[i][j][k]$ 为 $1$。此时可以用边权为 $1$ 的边将点 $i$ 和点 $j$ 连起来。
最后跑一遍最短路即可。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e2 + 10;
ll dp[maxn][maxn][maxn]; ll dis[maxn][maxn];
int main() { ios::sync_with_stdio(false); cin.tie(0); memset(dis, 0x3f, sizeof(dis)); int n, m; cin >> n >> m; for(int i = 0; i < m; ++i) { int x, y; cin >> x >> y; dp[x][y][0] = 1; dis[x][y] = 1; } for(int x = 1; x <= 64; ++x) { for(int k = 1; k <= n; ++k) { for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { if(dp[i][k][x - 1] && dp[k][j][x - 1]) { dp[i][j][x] = 1; dis[i][j] = 1; } } } } } for(int k = 1; k <= n; ++k) { for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); } } } cout << dis[1][n] << endl; return 0; }
|