acwing920. 最优乘车

t题目

题解

每一条公交上的线路都是通的，所以建图时可以将一条路线上的公交车设置为互通即可。题目求换乘最小次数，可转化为求乘车次数-1.
注意题目不能从右往左乘车，只考虑从左往右的情况

#include<iostream>
#include<cstring>
#include<sstream>
using namespace std;
const int N=510;
int n,m;
bool g[N][N];
int stop[N],dist[N];
int q[N];
void bfs(){
    memset(dist,0x3f,sizeof dist);
    int hh=0,tt=0;
    q[0]=1;
    dist[1]=0;
    while(hh<=tt){
        int t=q[hh++];
        for(int i=1;i<=n;i++){
            if(g[t][i]&&dist[i]>dist[t]+1){
                dist[i]=dist[t]+1;
                q[++tt]=i;
            }
        }
    }
}
int main(){
    cin>>m>>n;
    string line;
    getline(cin,line);
    while(m--){
        getline(cin,line);
        stringstream ssin(line);
        int cnt=0,p;
        while(ssin>>p)stop[cnt++]=p;
        for(int j=0;j<cnt;j++){
            for(int k=j+1;k<cnt;k++){
                g[stop[j]][stop[k]]=true;
            }
        }
    }
    bfs();
    if(dist[n]==0x3f3f3f3f)cout<<"NO"<<endl;
    else cout<<max(dist[n]-1,0)<<endl;
    return 0;
}