2022牛客多校训练第二场 L题 Link with Level Editor I

题目链接

Link with Level Editor I

题目大意

大概意思就是，给了我们$n$个世界，每个世界有$m$个点，每个世界中存在若干条有向边，会将某些点连起来。我们需要从1号点出发，最终走到$m$号点，每次可以选择在当前世界的当前点选择一条有向边出发走到另一个点，或者直接传送到下一个世界，题目问我们最小需要选择几个世界可以实现从1走到$m$。

题解

考虑DP，设$f_{i,j}$表示在第$i$个世界走到$j$点，最晚从哪个世界出发，由于题目卡内存了，我们需要使用滚动数组优化一下。并且还需要注意状态转移过程中的一些细节，假如当前的有向边是从1号点出发的，我们需要将当前最晚的世界写成$i$。具体看代码

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 2010, inf = 0x3f3f3f3f;
int f[2][maxn];
int n, m;
int main()
{
    
	cin >> n >> m;
	memset(f, -0x3f, sizeof f);
	int res = inf;
	for(int i = 1; i <= n; i ++){
    
		int num; cin >> num;
        f[(i - 1) & 1][1] = i;  // 尤其需要注意
		for(int j = 1; j <= m; j ++) f[i & 1][j] = f[(i - 1) & 1][j];
		while(num --) {
    
			int a, b; cin >> a >> b;
			f[i & 1][b] = max(f[i & 1][b], f[(i - 1) & 1][a]);
			if(b == m) res = min(res, i - f[i & 1][m] + 1);
		}
	}
	if(res >= inf / 2) cout << -1 << endl;
	else cout << res << endl;
}