题解

看完题目后第一感觉就是利用车站的编号来直接建图，但这是不正确的，因为没有体现换乘的次数，且建的边权值都为零，无法用最短路解决，于是用分层思想把问题转化为最短路问题。

怎么分层呢

其实就是把每条信息看成是一层

对于结点

考虑将每一个结点重新编号（不是输入的车站编号）。

然后建边

对于不同信息之间的结点（即不同层）

若之前的信息中有和当前车站编号相同的结点，那就与其连一条权值为1边，否则不连

对于同一信息之间的结点（即相同层）

向当前信息中的上一个结点建一条权值为零的边。当然，需要特判当前结点是否是第一个结点。

最后跑一遍最短路。我用的是堆优化的Dijkstra，以防spfa被卡

本题还需注意读入的问题，详尽内容见代码

参考程序

#include<bits/stdc++.h>
using namespace std;
struct e
{
	int to,next,w;
}edge[50001];//链式前向星存图
string s;
vector<int> anser;//即车站编号为n的结点在图中的编号
int n,m,letzt[501],k=1,head[50001],dist[501],cnt=0,f[501],minn=999999999,flag=-1;
priority_queue<pair<int,int> >q;//堆优化
void add(int u,int v,int w)//存边
{
	edge[++cnt].next=head[u];
	head[u]=cnt;
	edge[cnt].to=v;
	edge[cnt].w=w;
	return;
}
int main()
{
	memset(dist,-1,sizeof(dist));
	memset(letzt,-1,sizeof(letzt));
	scanf("%d%d",&m,&n);
	getline(cin,s);
	for(int  i=0;i<m;++i)
	{
		getline(cin,s);
		int flag=0;
		for(int j=0;j<s.length();++j)
		{
			int x=0;
			while(s[j]>'9'||s[j]<'0')//非数字部分
			{
				j++;
				if(j>=s.length())break;	
			}
			while(s[j]<='9'&&s[j]>='0'&&j<s.length())
			{
				x=x*10+s[j]-'0';
				j++;
			}
			flag++;//letzt数组存上一个车站编号为x的结点在图中的编号
			if(letzt[x]!=-1)add(k,letzt[x],1),add(letzt[x],k,1);
			letzt[x]=k;//变为现在的编号：k
			if(flag!=1)//是否是该信息中第一个结点
          add(k-1,k,0);建单向边
			if(x==n)anser.push_back(k);//该结点为终点站
			if(x==1)//该结点为起点站
			{
				q.push(make_pair(0,k));
				dist[k]=0;
			}
			k++;//编号加1
		}
	}
	while(!q.empty())//Dijkstra
	{
		int nun=q.top().second;
		q.pop();
		if(f[nun]==1)continue;
		f[nun]=1;
		for(int i=head[nun];i;i=edge[i].next)
		{
			int j=edge[i].to;
			if(dist[nun]+edge[i].w<dist[j]||dist[j]==-1)
			{
				dist[j]=dist[nun]+edge[i].w;
				if(!f[j])q.push(make_pair(-dist[j],j));
			}
		}
	}
	for(int i=0;i<anser.size();++i)
	{
		if(dist[anser[i]]!=-1)minn=min(minn,dist[anser[i]]),flag=1;
	}
	if(flag==-1)printf("NO");//不连通
	else printf("%d",minn);
	return 0;
}