L. Link with Level Editor I dp

L
dp

有 n n n 个世界，每个世界是一张简单有向图。从这些世界中选择一个子段进行游戏，规则为从 1 1 1 出发，每个世界可以原地不动或经过一条边，到达点 m m m 即为胜利。
要求选出一个尽可能短的子段，使得存在至少一种方案可以胜利。

记 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示到第 i i i 个世界中的 j j j 点最少需要经过多少个世界。答案即为 d p [ n ] [ m ] dp[n][m] dp[n][m] 。

考虑如何在第 i i i 个世界中到达 v v v ，只有如下两种转移方式：

1. 通过 u , v u,v u,v 从第 i − 1 i-1 i−1个世界中的 u u u 到达 v v v 。 d p [ i ] [ v ] = d p [ i − 1 ] [ u ] + 1 dp[i][v]=dp[i-1][u]+1 dp[i][v]=dp[i−1][u]+1
2. 不动，从第 i − 1 i-1 i−1 个世界中的 v v v 到达 v v v 。 d p [ i ] [ v ] = d p [ i − 1 ] [ v ] + 1 dp[i][v]=dp[i-1][v]+1 dp[i][v]=dp[i−1][v]+1

所以只需要依次对每个世界枚举所有边，用滚动数组优化即可。注意起点必须是1。

int n, m;
int dp[2][maxm];	//dp[i][j] 表示到第i个世界的第j个点最少要经过多少个世界
void solve() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
    	dp[0][i] = dp[1][i] = INF;
    }
    int ans = INF;
    int p = 0;
    for(int i = 1; i <= n; i++) {
    	int e;
    	cin >> e;
    	p ^= 1;
    	for(int j = 1; j <= m; j++) {
    		dp[p][j] = dp[p^1][j] + 1;
    	}
    	for(int j = 1; j <= e; j++) {
    		int u, v;
    		cin >> u >> v;
    		if(u == 1) {
    			dp[p][v] = 1;
    		}
    		else {
    			chmin(dp[p][v], dp[p^1][u] + 1);
    		}
    	}
    	chmin(ans, dp[p][m]);
    }
    if(ans == INF) {
    	cout << -1 << endl;
    }
    else {
    	cout << ans << endl;
    }
}