题目名称 | 267. [NOI 1997]最优乘车 |
---|---|
输入输出 | bustravel.in/out |
难度等级 | ★★ |
时间限制 | 1000 ms (1 s) |
内存限制 | 128 MiB |
测试数据 | 10 |
题目来源 | BYVoid 于2009-02-14加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:144, 提交:362, 通过率:39.78% | ||||
dateri | 100 | 0.000 s | 0.00 MiB | C++ |
521 | 100 | 0.000 s | 0.00 MiB | C++ |
syzhaoss | 100 | 0.000 s | 0.00 MiB | C++ |
锝镆氪锂铽 | 100 | 0.000 s | 0.00 MiB | C++ |
超人 | 100 | 0.000 s | 0.00 MiB | C++ |
devil | 100 | 0.002 s | 0.32 MiB | C++ |
苏轼 | 100 | 0.002 s | 0.42 MiB | Pascal |
Sky_miner | 100 | 0.003 s | 0.32 MiB | C++ |
woca | 100 | 0.003 s | 0.32 MiB | C++ |
donny | 100 | 0.003 s | 0.39 MiB | Pascal |
本题关联比赛 | |||
图论练习和一些常规题 | |||
图论练习和一些常规题 |
关于 最优乘车 的近10条评论(全部评论) | ||||
---|---|---|---|---|
以为每行数据后都有一个空格,想了好久没想到解决方案。。。
结果测试点没有这个问题!!! | ||||
这题读入两颗星,其他没有技术含量
| ||||
读入简直跟吃了****一样难受
devil
2015-10-19 10:14
7楼
| ||||
打了一个97行的SPFA 最后到达不了还输出-1。。。而且数组还开小了
| ||||
字符串还要多加练习
| ||||
mark之
| ||||
这道题就是考读入= =....
| ||||
Floyd算法即可過全。我用裸的floyd算法,總耗時0.3秒。
只是讀入時有些困難。 詳細:http://www.yeefanblog.tk/2011/11/noi1997-bustravel.html | ||||
ld
QhelDIV
2012-03-25 15:17
1楼
|
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行依次给出了第1条到第M条巴士线路的信息。其中第 i+1行给出的是第i条巴士线路的信息,从左至右按运行顺序依次给出了该线路上的所有站号相邻两个站号之间用一个空格隔开。
输出文件只有一行。如果无法乘巴士从饭店到达S公园,则输出"N0",否则输出你的程序所找到的最少换车次数,换车次数为0表示不需换车即可到达
输入文件
3 7 6 7 4 7 3 6 2 1 3 5
输出文件
2