Niuke multi school link with level editor i- (linear DP)

L

The question ：
It's for you. n A world , Every world has m A little bit , Then every world has some directional edges . When you are in this world , You can either stop at this point , Or walk to the point you can reach . Then the next second you will be transmitted to the next world , Where you are ID It won't change . Now let you choose a continuous world , And then you can go from 1 Go to No m Number point . Ask how many worlds you choose at least . If there is no answer output -1.

reflection ：
1. At first I thought the title meant , Just choose some worlds in order , No need to be continuous . If so , Can define dp[i][j] by , Used the second i A world , To j Minimum cost of points . What we need to clarify here is ： Not in the first i In a world , To j spot . But before this i One world to j Select at least a few worlds . So when updating , Update the minimum value directly from the upper layer . And then update to this page i The minimum cost of the right end of the world . Note that comments are made in the code .
2. The meaning of the correct question is continuous , Then you can't take the minimum cost like this . If in each i It's so complicated to point to dichotomy n×n×log(n). Then think dp. Can define dp[i] by , All can be from 1 Go to the i The largest subscript in 1 The subscript . Then when updating, update first maxn Array , See what points can be reached in the path of the world . And then update it dp, If at this time m Point is reached , Then the cost is i-dp[m]+1. Is to use the i It can only be reached when there is a world , Then take a look at the recent ones that can come 1 Where is it .

Code ：

 Can be discontinuous code ：
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 1e4+10,M = 2e3+10;

int T,n,m,k;
int va[N];
int dp[N][M]; // To the first i A world , To j Minimum cost of points 
int minn[N];

vector<PII > v[N];

int solve()
{
    
	mem(dp,0x3f);
	for(int i=1;i<=n;i++)
	{
    
		dp[i][1] = min(dp[i][1],1ll); // To 1 The cost is 1
		for(int j=1;j<=m;j++) dp[i][j] = min(dp[i][j],dp[i-1][j]); // arrive j Minimum cost of points ( Not necessarily in this world )
		for(auto t:v[i])
		{
    
			if(t.fi==1) dp[i][t.fi] = dp[i][t.se] = 1; // Special attention 
			else dp[i][t.se] = min(dp[i][t.se],dp[i-1][t.fi]+1); // If in the first place i A world arrives t.se spot , Then what is the minimum cost .
		}
	}
	if(dp[n][m]>1e9) return -1;
	else return dp[n][m];
}

/*  Because only one layer at a time , You can use scrolling arrays to optimize space . int solve() { mem(dp,0x3f); for(int i=1;i<=n;i++) { dp[i&1][1] = min(dp[i&1][1],1ll); for(int j=1;j<=m;j++) dp[i&1][j] = min(dp[i&1][j],dp[(i-1)&1][j]); for(auto t:v[i]) { if(t.fi==1) dp[i&1][t.fi] = dp[i&1][t.se] = 1; else dp[i&1][t.se] = min(dp[i&1][t.se],dp[(i-1)&1][t.fi]+1); } } if(dp[n][m]>1e9) return -1; else return dp[n][m]; } */

signed main()
{
    
	IOS;
	cin>>n>>m;
	for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) dp[i][j] = inf;
	for(int i=0;i<=m;i++) minn[i] = inf;
	for(int i=1;i<=n;i++)
	{
    
		cin>>k;
		while(k--)
		{
    
			int a,b;
			cin>>a>>b;
			v[i].pb({
    a,b});
		}
	}
	cout<<solve()<<"\n";
	return 0;
}

 Must be continuous code ：
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 1e4+10,M = 2e3+10;

int T,n,m,k;
int va[N];
int dp[M]; // Can walk to i One of the biggest 1 The subscript .
int maxn[M];

vector<PII > v[N];

signed main()
{
    
	IOS;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
    
		cin>>k;
		while(k--)
		{
    
			int a,b;
			cin>>a>>b;
			v[i].pb({
    a,b});
		}
	}
	int minn = inf;
	for(int i=1;i<=n;i++)
	{
    
		dp[1] = i; // Every world can go to 1
		for(auto t:v[i]) maxn[t.se] = max(maxn[t.se],dp[t.fi]); // Use the upper layer dp to update maxn
		for(int j=1;j<=m;j++) dp[j] = max(dp[j],maxn[j]); // Update again dp
		if(dp[m]) minn = min(minn,i-dp[m]+1); // If you come to the i A world , Can walk to m 了 , The answer is the latest 1 Go to the i Cost 
	}
	if(minn==inf) cout<<-1;
	else cout<<minn;
	return 0;
}

summary ：
Think more , clarify dp State definition of .