AcWing 920. 最优乘车
原题链接
中等
作者:
Ehv
,
2024-04-07 21:42:04
,
所有人可见
,
阅读 5
记录一下从字符串中分割出数字的方法
//getline()之后继续使用getline(),不用清空缓冲区,cin和scanf后面使用getline(),需要使用cin.ignore()清空缓冲区
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m;
int x,len;
int a[N];
string s;
int w[N][N],dis[N];
bool visi[N];
queue<int>q;
void bfs() {
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
q.push(1);
visi[1]=1;
while(!q.empty()) {
int t=q.front();
q.pop();
for(int i=1; i<=n; i++) {
if(w[t][i]&&!visi[i]) {
dis[i]=dis[t]+1;
visi[i]=1;
q.push(i);
}
}
}
}
int main() {
scanf("%d%d",&m,&n);
cin.ignore();//清空缓冲区的回车符
for(int i=1; i<=m; i++) {
len=0;
getline(cin,s);//首先读入一行带空格的字符串
stringstream line(s);//初始化一个stringstrem对象
while(line>>x)a[++len]=x;//将string流中的每个数据取出,赋值给x,并且存储在数组中
for(int i=1; i<=len; i++) {
for(int j=i; j<=len; j++)w[a[i]][a[j]]=1;
}
}
bfs();
if(dis[n]==0x3f3f3f3f)puts("NO");
else cout<<dis[n]-1;
return 0;
}