其他老师数据结构优乘车.pdfVIP

————————————————————————————————————

最优乘车。为了简化城市公共汽车系统，某城市决定对大部分的公共汽车都采用一

票制，但由于某些公共汽车所经过的停车站太多和路途太长，就采用两票或多票制。经过这

种票制后，人们坐公共汽车从一个站到另一个站时，就不得不选择一个好的乘车方案，

以使他们的乘车费用最低。

为了方便出最佳的乘车方案，我们假设：

（1）采用一票制的公共汽车，无论从哪个站上车到那个站下车，乘该公共汽车的费用

为1（费用单位）。

（2）采用多票制的公共汽车，将设立某些站为关键站；那么，如果乘该路公共汽

车从A站到B站时，不经过任何关键站的乘车费用为1，而经过K个关键站的乘车费用为

K+1；所谓经过关键站是指：乘该路公共汽车时，该关键站是其途中的一个站，但它不是上

车站也不是下车站；例如，某路公共汽车经过1，2，3，4，*5，6，7，8，9；其中5是关键

站，那么，从5站上车到9站下车或从2站上车到5站下车的费用为1，而从4站上车到6

站下车的费用将是2。

（3）所有公共汽车都是双向行驶的，也即如果公共汽车经过的站点有A和B，那么，

你可以乘该公共汽车从A到B或从B到A。

你的任务就是：对于输入文件中给出的公共汽车各停车站，和某乘客的起点站A和终

点站B，请你编程为乘客求出最佳的乘车方案，使得他的乘车费用最少。

输入：第1行为N、R、A和B，其中N为城市公共汽车停车站的总个数，这些停车站

被统一编号为1、2、……、N；R为公共汽车总路数。A为起点站的编号，B为终点站的编

号。（1≤N≤1000，1≤R≤300，每路公共汽车的最多站点数为20）。数据之间用空格分开。

第2行到R+1行的每一行为一路公共汽车经过的停车站编号，停车站编号的排列顺序

是该路公共汽车按一个方向行车顺序依次经过的停车站，如为关键停车站，则其编号的前面

有一个*。每行数据之间用空格分开。

输出：从A站到B站所需的最少费用。如果不能乘这些公共汽车从A到B，输出-1。

输入输出示例：INPUT4.TXTOUTPUT4.TXT

1241123

123*4567

1238

8459

765*9101112

【分析】这一道试题与NOI’97的Travel问题有一定的相似之处，都是先通过建立图模

型然后利用求最短路的算法解题。在建立图模型的过程当中大致思想也是相同的，但是这到

题目当中结点的个数达到了1000个，很显然是不能够采用邻接矩阵来表示的，至于邻接表，虽

然上没有多大问题，但是公共汽车的线路较多，自然任意两个车站之间的路径数也相对

较大，再加上对于指针的操作又比较耗时，因此也是不行的。

唯一的方法是简单的记录下所有的公共汽车路线，但为了减少在利用Dijkstra算法解题

当中的耗时，可先对每一条公共汽车线路进行预处理，建立一个关于该路线的矩阵，用ai,j,k

表示第k条路线上的第i个车站到第j个车站通过该路线连接所需要的花费，这些矩阵

在空间上是可以满足的。这样，在利用Dijkstra算法解题的过程当中，每查找到一个耗费最

小的车站以后，再根据每一条线路查找与之相连的车站之间的花费。直到最后查找出的花费