[diary of supplementary questions] [2022 Niuke summer multi school 2] l-link with level editor I

Pro

https://ac.nowcoder.com/acm/problem/239349

Sol

With $f_{i,j}$ Said in the first i The world is... In the end j A little bit , Which world can we start from at the latest .

State transition equation ： If there is one in a world x->y The edge of , that $f_{i,y}=max(f_{i-1,y},f_{i-1,x})$, The first dimension is only related to the previous world , You can use the rolling array to optimize .

The difficulty of this problem lies in the following code ：f[(i-1)&1][1] = i;Fo(j,1,m) f[i&1][j] = f[(i-1)&1][j]; And f[i&1][1] = i; Fo(j,2,m) f[i&1][j] = f[(i-1)&1][j]; Is it equivalent .

Why do you think so ？ Because it's easy to understand , The first i The third in the world 1 The number point can be determined by i-1 The third in the world 1 It's time to come , I mistakenly think here f[(i-1)&1][1] = i; Just right $f_{i,x}$ Assign initial value to , So I will write the code of the latter .

In fact, through testing the sample and careful debugging, we can find , This is not just about assignment , And it is also related to the update below , Therefore, the understanding here can be ： The first i A world can be the beginning of the whole level , Arrive in this world at this time 1 The latest world at point is i. Why don't you consider taking the 1 Node number as the start ？ Actually, I've finished thinking about it ：

Suppose that in the front of a certain world 1 Node as the beginning of the level , If every world in front chooses 1 Node is no. , Until you select to i A world 1 Node is no. , At this time, it's better to directly select the i The number node of the world is better ; If every world ahead has a path to move , Then arrive at the i The node number of universal time must not be 1, That is, in the interval [2,m] It must contain the previous world 1 Node number as the starting case . Therefore, we need a key code f[(i-1)&1][1] = i;

Code

//By cls1277
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define endl '\n'

// const LL maxn = ;

int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef DEBUG
    freopen("data.txt","r",stdin);
    #endif
    LL n, m, ans=INT_MAX; cin>>n>>m;
    vector<vector<LL>> f(2, vector<LL>(m+1, -INT_MAX));
    Fo(i,1,n) {
    
        LL l; cin>>l;
	    f[(i-1)&1][1] = i;
	    Fo(j,1,m) f[i&1][j] = f[(i-1)&1][j];
// f[i&1][1] = i;
// Fo(j,2,m) f[i&1][j] = f[(i-1)&1][j];
        Fo(j,1,l) {
    
            LL x, y; cin>>x>>y;
            f[i&1][y] = max(f[i&1][y], f[(i-1)&1][x]);
            if(y==m&&f[i&1][m]!=-INT_MAX) ans = min(ans, i-f[i&1][m]+1);
        }
    }
    cout<<(ans==INT_MAX?-1:ans);
    return 0;
}