来一份97年的NOI题

今天的问题是关于图形结构的，但是如果各位愿意的话，BFS也应该可以做。

点开下面的音乐，开启今天的内容吧！

今天的题目是一个基本的dijkstra图形数据题。代码量中等，其实使用广度优先也是可以做出来的，搜索量初步估计相差不大（要是估摸不准，也就差一两个数量级，“问题不大”），具体题目如下

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

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

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

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

初步看这个题，我想，这不就是地图导航干的事情吗？于是我到洛谷上一查才发现，这原来是1997年的OI题······

上古老题了啊！而且它居然预测到了现代的地图的导航技术，这就真的很神奇了。

对于这道题而言，一大难点就在于输入的方法。相信大家向来最讨厌这种长度提前不说并且不固定的输入，关键还都是数据！这就要求我们能够去从数据和空格的混杂体中提取有用的数据出来，并且转化到数组里面备用。我个人就是在这一点被卡死的······

输入数据的时候我从某个大牛那里学到了一招：先将前面的两个m和n用cin或者scanf进行输入，再写一个getline，这样的话我们就可以在输入数据后放心回车啦！

再输入线路信息的时候，我的方案是就开一个字符串，然后将字符串信息转化成图形数据结构（邻接矩阵）进行存储，然后再次输入，再转化，以此直到输入完所有的数据为止。

具体的建图方法是：把一条线路的每一个站点都和该站前面的所有站点建立有向边，得到一个可以模拟城市公交系统的图。

但是，我的踩坑点就在数据的转化上。

当测评机输入完了一行路线数据后，接下来的字符是什么?这个我是不知道的。但是我觉得这个格子一定是'\0'或者'  '之一，但是事实却真的不是这样的，于是乎我就爆0了。

解决方案是将我在上图程序中画出来的判定机制进行一些改变，从要求改字符不是\0或者空格改成只能是数字类型的数据，这样就很好的解决了这个问题。如改成line[t]<='9'&&line[t]>='0';

存图的时候由于这道题里面的公交线路存在重叠的问题，所以邻接表的使用就会很困难，从我个人的感觉看，邻接矩阵是明显更好的选择。如果邻接表不判重就会凭空增加计算量。这就很不划算了（但是说实在话，我个人觉得邻接表在遍历时会稍微快一点，访问一条边用邻接表就很慢）

存完图，就是一个非常基本的dijkstra了。我们在邻接表中只需要把有连接的边设置为1，其他部分设置为0x3f3f3f3f就可以正常进行计算了。

最后提醒一点：输出的时候数据一定-=1，因为我们实际上算的是乘坐公交的次数，换车次数就是乘坐次数减去1。遇上0x3f就输出NO，意味着坐车到不了。

最后，呈现一下我的代码

今天的文章就到这里啦！记得三连哦~