(2022牛客多校二)L-Link with Level Editor I（动态规划）

题目：

样例1输入：

3 3
1
2 1
1
2 3
1
1 2

样例1输出：

-1

样例2输入：

3 3
1
2 1
1
1 2
1
2 3

样例2输出：

2

题意：有n个世界，每个世界有n个点，编号从1~n，m条边，我们可以从这些世界中选择一个子段进行游戏，规则为从任意一个世界的1出发，每个世界可以原地不动或者经过一条边走到另一个位置，在此操作后会直接传送到下一个世界的相同编号的点，到达点m即为胜利。要求选出一个尽可能短的子段，使得存在至少一种方案可以胜利，如果走不到m点就输出-1.

注意：

（1）我们最后求的答案就是路径所经过的世界个数，而不是路径长度和

（2）内存很小，不能建图去做

（3）可以从任意一个世界的1号点出发

（4）只能从编号较小的世界前往编号较大的世界

分析：设f[i][j]表示到达第i个世界的j点的路径所经过世界的个数最小值，那么答案min(f[i][m])（1<=i<=n）

更新的话也比较简单，第i个世界的j点可以由第i-1个世界的j点到达，也可以由第i-1个世界的u点到达，前提是存在边(u,j)

需要注意的一点是对于任意一层i，都有f[i][1]=0，那么我们直接变读入边更新即可，在过程中记录f[i][m]的最小值即可。

上面思路是正确的，但是由于内存问题，所以无法二维数组实现，只能通过滚动数组优化实现，由于我们更新当前世界的数组只需要利用上一层世界的数组，所以我们只要开两个数组分别记录当前层和上一层的数据即可，即：f[i]记录的是到达当前世界i点需要的最小传送次数，g[i]记录的是到达上一世界i点需要的最小传送次数，这样我们就可以通过滚动数组迭代求出答案。

下面是代码：
 

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e4+10;
int f[N],g[N];//这两个数组相当于滚动数组 
//f[i]记录的是到达当前世界i点需要的最小传送次数
//g[i]记录的是到达上一世界i点需要的最小传送次数
int main()
{
	int n,m;
	cin>>n>>m;
	int ans=0x3f3f3f3f;
	memset(g,0x3f,sizeof g);
	g[1]=0;
	for(int i=1;i<=n;i++)
	{
		memset(f,0x3f,sizeof f);
		int t,u,v;
		scanf("%d",&t);
		for(int j=1;j<=t;j++)//通过上一个世界的u点走到v点并传送到当前世界
		{
			scanf("%d%d",&u,&v);
			f[v]=min(f[v],g[u]+1);
		}
		for(int i=1;i<=n;i++)//上一个世界的点直接不动，直接传送到当前世界
			f[i]=min(f[i],g[i]+1);
		ans=min(ans,f[m]);
		memcpy(g,f,sizeof f);//数组滚动 
		g[1]=0;//从任意一个世界的1号点开始
	}
	if(ans!=0x3f3f3f3f) printf("%d",ans);
	else printf("-1");
	return 0;
}