最优乘车（简单最短路）

传送门：最优乘车

思路；每一条路径上前面的点到后面的距离都是1，可以转换成最短路问题，最后求出的次数是最小乘车次数，减1就是最小换乘次数。

注意输入较特殊，用stringstream输入流进行输入

代码：

#include<iostream>
#include<cstring>
#include<sstream>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N=3010;
int d[N][N];
int dist[N];
int n,m;
int q[N];
void bfs()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    int hh=0,tt=1;
    q[0]=1;
    while(hh!=tt)
    {
        int t=q[hh++];
        if(hh==N)
            hh=0;
        for(int i=1;i<=m;i++)
        {
                if(dist[i]>dist[t]+1&&d[t][i])
                {
                    dist[i]=dist[t]+1;
                    q[tt++]=i;
                    if(tt==N)
                    tt=0;
                }
        }
    }
}
int main()
{
    string b;
    cin>>n>>m;
    int a[510];
    int cnt=1;
    getchar();
    for(int i=1;i<=n;i++)
    {
        getline(cin,b);
        stringstream ssin(b);
        int cnt=1,p;
        while(ssin>>p) a[cnt++]=p;
        for(int i=1;i<cnt;i++)
            for(int j=i+1;j<cnt;j++)
                d[a[i]][a[j]]=1;
    }
    bfs();
    if(dist[m]>=0x3f3f3f3f)
        cout<<"NO";
    else
        cout<<max(dist[m]-1,0);
 
    return 0;
}