地狱把妹王太好看啦!orz散人!

其实不应该有这破题的

首先我们考虑这个题是不是很像臻大佬之前出的某个题啊

然后我们可以考虑建图然后跑最短路

怎么建?考虑不管哪个路线,把某个点下一步能走到的所有点都连个边

然后$dp[i][j]$表示走到i号点,处于路线j的最小换乘次数,然后转移时如果下一条边不是j中的就相应的换一下

这里提供一种更优美的做法

显然同一路线上,前面的点能到达所有后面的点,那么我们可以把这n^2点对连有向边,边权为1

然后d[i][i]=0,其他初始化为inf,跑一遍Floyd

这样你会发现答案就是从1~n的最短路-1

正确性显然吧

本题最大的坑点在于狗屎般的输入,你需要特判回车,而最后一行没有回车!!!

而且回车是/r

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN = 600;
int n, m, flg;
int d[MAXN][MAXN];
vector<int> a[MAXN];

namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
	bool IOerror = 0;
	inline char nc() {
		if(IOerror)return '\r';
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
			if(p1 == pend) {
				IOerror = -1;
				return '\r';
			}
		}
		return *p1++;
	}
	inline int read() {
		char s = nc();
		int x = 0;
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		if(s == '\r')flg = 0;
		return x;
	}
}
using namespace fastIO;

int main() {
	m = read();
	n = read();
	for(int i = 1, qwq; i <= m; ++i) {
		flg = 1;
		while(qwq = read()) {
			a[i].push_back(qwq);
			if(!flg)break;
		}
	}
	memset(d, 0x3f3f3f3f, sizeof(d));
	for(int i = 1; i <= m; ++i) {
		for(int j = 0; j < a[i].size(); ++j) {
			for(int k = j + 1; k < a[i].size(); ++k) {
				d[a[i][j]][a[i][k]] =  1;
			}
		}
	}
	for(int i = 1; i <= n; ++i) {
		d[i][i] = 0;
	}
	for(int k = 1; k <= n; ++k) {
		for(int i = 1; i <= n; ++i) {
			for(int j = 1; j <= n; ++j) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	if(d[1][n] > 10000)puts("NO");
	else printf("%d\n", d[1][n] - 1);
	return 0;
}