之后每次迭代t^1 使得 0->1 1->0
这里有 n个世界,每个世界都有 m 个点。
在i个世界中,你最多可以选择一条边 ,从 u点 移动到 v点 (可以选择不移动)。随后进入到第 i+1 个世界中的点 。如果选择在 u 点上不移动,则进入到第 i+1 个世界的u点 。
找到一段连续的世界 ,使得可以从点 1到点m 。最小化 r-l+1 (区间长度)
dp[i][j]表示在i个世界(i是滚动式呈现)到达点j,路过的最小世界数
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10, INF = 0x3f3f3f3f;
int dp[2][N]; //因为第i个状态只取决第i-1状态,所以第一维可以用滚动数组承接上一个状态
int n, m;
int ans = INF;
int main()
{
cin>>n>>m;
for(int i = 2; i <= m; i ++ ) dp[0][i] = dp[1][i] = n + 1; //初始化
for(int i = 1, t = 1; i <= n; i ++ , t ^= 1){
//f[1][2]=min(f[0][2]+1, n+1)
//第一部相当于从f[0][2]状态转移而来,所以会承接0
int cnt;
cin>>cnt;
for(int u =2; u <= m; u ++ ) dp[t][u] = min(dp[t^1][u] + 1, n + 1); //更新最短步数是不是由上一个世界相同的点i转移来的
for(int j = 1; j <= cnt; j ++ ){
int u, v;
cin>>u>>v;
dp[t][v] = min(dp[t][v], dp[t ^ 1][u] + 1); //f[t^1][u]+1表示上一个世界到达u点的代价
}
ans = min(ans, dp[t][m]); //第二维表示点,第一维用于滚动式记录世界
}
if(ans > n) ans = -1;
cout<<ans<<endl;
return 0;
}
标签:尝试,状态,int,压缩,世界,滚动式,ans,dp
From: https://www.cnblogs.com/liang302/p/16600656.html