L
dp
题意
有
n
n
n 个世界,每个世界是一张简单有向图。从这些世界中选择一个子段进行游戏,规则为从
1
1
1 出发,每个世界可以原地不动或经过一条边,到达点
m
m
m 即为胜利。
要求选出一个尽可能短的子段,使得存在至少一种方案可以胜利。
思路
记 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示到第 i i i 个世界中的 j j j 点最少需要经过多少个世界。答案即为 d p [ n ] [ m ] dp[n][m] dp[n][m] 。
考虑如何在第 i i i 个世界中到达 v v v ,只有如下两种转移方式:
- 通过 u , v u,v u,v 从第 i − 1 i-1 i−1个世界中的 u u u 到达 v v v 。 d p [ i ] [ v ] = d p [ i − 1 ] [ u ] + 1 dp[i][v]=dp[i-1][u]+1 dp[i][v]=dp[i−1][u]+1
- 不动,从第 i − 1 i-1 i−1 个世界中的 v v v 到达 v v v 。 d p [ i ] [ v ] = d p [ i − 1 ] [ v ] + 1 dp[i][v]=dp[i-1][v]+1 dp[i][v]=dp[i−1][v]+1
所以只需要依次对每个世界枚举所有边,用滚动数组优化即可。注意起点必须是1。
代码
int n, m;
int dp[2][maxm]; //dp[i][j] 表示到第i个世界的第j个点最少要经过多少个世界
void solve() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
dp[0][i] = dp[1][i] = INF;
}
int ans = INF;
int p = 0;
for(int i = 1; i <= n; i++) {
int e;
cin >> e;
p ^= 1;
for(int j = 1; j <= m; j++) {
dp[p][j] = dp[p^1][j] + 1;
}
for(int j = 1; j <= e; j++) {
int u, v;
cin >> u >> v;
if(u == 1) {
dp[p][v] = 1;
}
else {
chmin(dp[p][v], dp[p^1][u] + 1);
}
}
chmin(ans, dp[p][m]);
}
if(ans == INF) {
cout << -1 << endl;
}
else {
cout << ans << endl;
}
}