AcWing 920. 最优乘车
原题链接
中等
作者:
十六
,
2021-01-23 11:25:07
,
所有人可见
,
阅读 499
#include<bits/stdc++.h>
using namespace std;
const int N = 500+5;
int m, n;
bool g[N][N];
int tmp[N];
int dis[N];
void bfs(){
memset(dis, -1, sizeof dis);
queue<int> q;
q.push(1); dis[1] = 0;
while(q.size()){
int t = q.front();
q.pop();
for(int i=1; i<=n; i++){
if(g[t][i] && dis[i]==-1){
dis[i] = dis[t]+1;
if(i==n) return ;
q.push(i);
}
}
}
}
int main(){
scanf("%d%d\n", &m, &n);
string s;
while(m--){
getline(cin, s);
stringstream in(s);
int cnt = 0;
while(in>> tmp[cnt]) cnt++;
for(int i=0; i<cnt; i++){
for(int j=i+1; j<cnt; j++){
g[tmp[i]][tmp[j]] = true;
}
}
}
bfs();
if(dis[n]==-1) puts("NO");
else cout<< max(dis[n]-1, 0)<< endl;
return 0;
}