(2022 Niuke multi School II) l-link with level editor I (dynamic planning)

subject ：

Examples 1 Input ：

3 3
1
2 1
1
2 3
1
1 2

Examples 1 Output ：

-1

Examples 2 Input ：

3 3
1
2 1
1
1 2
1
2 3

Examples 2 Output ：

2

The question ： Yes n A world , Every world has n A little bit , Number from 1~n,m side , We can choose a sub segment from these worlds to play , The rule is from any world 1 set out , Each world can stay where it is or go through one side to another , After this operation, it will be directly transmitted to the point with the same number in the next world , Arrival point m It's victory . It is required to select a sub paragraph as short as possible , So that there is at least one solution that can win , If you can't get there m Click to output -1.

Be careful ：

（1） The final answer we seek is the number of worlds the path passes through , Instead of path length and

（2） Memory is very small , Can't build a map to do

（3） From any world 1 Starting at No

（4） You can only go from the world with smaller number to the world with larger number

analysis ： set up f[i][j] It means to arrive at the third i A world j The minimum number of worlds the path of a point passes through , So the answer min(f[i][m])（1<=i<=n）

The update is also relatively simple , The first i A world j Point can be determined by i-1 A world j O 'clock , It can also be determined by i-1 A world u O 'clock , The premise is that there is an edge (u,j)

One thing to note is that For any layer i, There are f[i][1]=0, Then we can directly change the read in side to update , Record in the process f[i][m] The minimum value of .

The above idea is correct , But due to memory problems , Therefore, two-dimensional arrays cannot be implemented , It can only be achieved by rolling array optimization , As we update the array of the current world, we only need to use the array of the previous world , So we just need to open two arrays to record the data of the current layer and the previous layer respectively , namely ：f[i] The record is to arrive at the current world i The minimum number of transfers required for a point ,g[i] The record is to arrive at the last world i The minimum number of transfers required for a point , In this way, we can iterate through the rolling array to find the answer .

Here is the code ：
 

#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];// These two arrays are equivalent to rolling arrays  
//f[i] The record is to arrive at the current world i The minimum number of transfers required for a point 
//g[i] The record is to arrive at the last world i The minimum number of transfers required for a point 
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++)// Through the last world u Go to v Click and send to the current world 
		{
			scanf("%d%d",&u,&v);
			f[v]=min(f[v],g[u]+1);
		}
		for(int i=1;i<=n;i++)// The point of the last world doesn't move directly , Directly to the current world 
			f[i]=min(f[i],g[i]+1);
		ans=min(ans,f[m]);
		memcpy(g,f,sizeof f);// Array scrolling  
		g[1]=0;// From any world 1 It starts at the fifth 
	}
	if(ans!=0x3f3f3f3f) printf("%d",ans);
	else printf("-1");
	return 0;
}