华师一附中OI组

标题: P5767 [NOI1997] 最优乘车 [打印本页]

作者: admin 时间: 2021-5-17 21:06
标题: P5767 [NOI1997] 最优乘车
https://www.luogu.com.cn/problem/P5767

题目描述
H 城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。

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

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

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

输入格式
第一行有两个数字 M 和 N（1≤M≤100，1<N≤500），表示开通了 M 条单程巴士线路，总共有 N 个车站。

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

输出格式
只有一行。如果无法乘巴士从饭店到达 S公园，则输出 NO ；

否则输出你的程序所找到的最少换车次数，换车次数为 0 表示不需换车即可到达。

输入输出样例
输入 #1复制
3 7
6 7
4 7 3 6
2 1 3 5
输出 #1复制
2

作者: admin 时间: 2021-5-17 21:08
NOI1997，那年好像是在香港举行吧，我没能去。倒是2000在澳门的时候我去了广州，好年轻的时候。
这个提很很多的做法，这里我们先试着用最简单的最短路径的方法，

作者: admin 时间: 2021-5-17 21:11
先读入数据，高手会快读的话知道如何读入这些没有个数的数，一般的同学就有点为难了，这个我给大家写出来，把每条线路读进来。

void read()
{
cin>>m>>n;
string s;
getline(cin,s);
for (int i=1; i<=m; i++)
{
getline(cin,s);
int l=s.size();
int x=0,k=1;
int p=0;
while (p<=l-1)
{
char ch=s[p];
while (ch>='0' && ch<='9')
{
x=10*x+(ch-'0');
p++;
ch=s[p];
}
a[i][k]=x;
k++;
p++;
x=0;
}
}
}

复制代码

欢迎光临华师一附中OI组 (http://hsyit.cn/)