AcWing920最优乘车

题目地址：https://www.acwing.com/problem/content/922/

题目描述：

H城是一个旅游胜地，每年都有成千上万的人前来观光。

为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。

每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。

一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。

现在用整数1,2,…N 给H城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为1，S公园巴士站的编号为N。

写一个程序，帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程中换乘的次数最少。

输入格式

第一行有两个数字M和N，表示开通了M条单程巴士线路，总共有N个车站。

从第二行到第M+1行依次给出了第1条到第M条巴士线路的信息，其中第i+1行给出的是第i条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号，相邻两个站号之间用一个空格隔开。

输出格式

共一行，如果无法乘巴士从饭店到达S公园，则输出”NO”，否则输出最少换乘次数，换乘次数为0表示不需换车即可到达。

数据范围

1≤M≤100
1≤N≤500

题解：假设给出一条线路：5 4 6 2，那么我们就可以构造有向边：5-4,5-6,5-2,4-6,4-2,6-2,这样从1到n的最短路就是需要乘坐的次数，减1就是最后的结果。可以直接使用bfs进行求解。

AC代码：

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring> 
#include<sstream>
#include<queue>
using namespace std;
const int N=510;
int graph[N][N];

int BFS(int s,int t){
    if(s==t) return 1;
    queue<pair<int,int> >q;
    q.push(make_pair(0,s));
    int p[N]={0};
    p[s]=1;
    while(!q.empty()){
        pair<int,int>now;
        now=q.front();q.pop();
        if(now.second==t) return now.first;
        for(int i=1;i<=t;i++){
            if(graph[now.second][i]==1){
                if(p[i]==0) {
                    q.push(make_pair(now.first+1,i));
                    p[i]=1;
                }
            }
        }
    }
    return -1;
}

int main(){
    int m,n;cin>>m>>n;
    memset(graph,0x3f,sizeof(graph));
    string line;
    getline(cin,line);
    int stop[N],cnt=0;
    while(getline(cin,line)){
        cnt=0;
        stringstream ss(line);
        while(ss>>stop[cnt++]) ;
        cnt--;
        for(int i=0;i<cnt-1;i++){
            for(int j=i+1;j<cnt;j++){
                graph[stop[i]][stop[j]]=1;
            }
        }
    }
    int ans=BFS(1,n);
    if(ans==-1) cout<<"NO";
    else cout<<ans-1;
    return 0;
}

写于：2020/9/3 18:54