思路
例如
6 7
4 7 3 6
2 1 3 5
每组之间的边互相相连,连通标记为true(连通的边权都是1),所以问题就变成了1~7的最短距离,最终答案就是最短距离-1
忽略空格读一行数据
string line;
getline(cin,line);
stringstream ssin(line);
int x
while(ssin>>x);
#include<cstring>
#include<algorithm>
#include<sstream>
#include<iostream>
#include<queue>
using namespace std;
const int N=510;
int n,m;
bool g[N][N];
int dist[N];
int stop[N];
queue<int>q;
string line;
int bfs()
{
q.push(1);
memset(dist,0x3f,sizeof dist);
dist[1]=0;
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=1;i<=n;i++)
if(g[t][i]&&dist[i]>dist[t]+1)
{
dist[i]=dist[t]+1;
q.push(i);
}
}
return dist[n];
}
int main()
{
cin>>m>>n;
getline(cin,line);//去除回车
while(m--)
{
getline(cin,line);
stringstream ssin(line);
int p,cnt=0;
while(ssin>>p) stop[++cnt]=p;
for(int i=1;i<=cnt;i++)
for(int j=i+1;j<=cnt;j++)
g[stop[i]][stop[j]]=true;
}
int ans=bfs();
if(ans==0x3f3f3f3f) puts("NO");
else cout<<max(ans-1,0)<<endl;
}