[NOI 1997] 最优乘车

知识点

图建模、广度优先搜索、最少换乘

解题思路

对每条单向线路，将前面的每站向后面的每站连一条边，表示乘一辆车可达。原站1做BFS，得到最少乘车次数，到终点后减1即换乘次数；不可达输出NO。

正确性说明

一次合法乘车对应某线路由较早站到较晚站，恰与一条建模边对应；反之每条边都能用一辆车实现。故图中边数最短路等于最少乘车次数。至少乘一次才能由1到不同终点N，因此减1恰为换乘数。

易错点

线路单向，不能逆走；输入每条线路长度不固定，按整行读取；一车经过多站也只算一次乘车。

复杂度

N站、各线路长度Li，建图O(ΣLi²)，矩阵BFS O(N²)，空间O(N²)，N≤500。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int M,N;cin>>M>>N;string line;getline(cin,line);vector<vector<char>>g(N+1,vector<char>(N+1));for(int z=0;z<M;z++){getline(cin,line);stringstream ss(line);vector<int>a;int x;while(ss>>x)a.push_back(x);for(int i=0;i<(int)a.size();i++)for(int j=i+1;j<(int)a.size();j++)g[a[i]][a[j]]=1;}vector<int>d(N+1,-1);queue<int>q;d[1]=0;q.push(1);while(!q.empty()){int u=q.front();q.pop();for(int v=1;v<=N;v++)if(g[u][v]&&d[v]<0)d[v]=d[u]+1,q.push(v);}if(d[N]<0)cout<<"NO\n";else cout<<d[N]-1<<'\n';}