【大作业】城市地铁线路最短路规划及路径输出（满分）

成都市地铁路线图可以看作是一个有环无向图。 根据老师提供的成都地铁路线图，我一共划分了5条可行路线，并沿途标记了56个站点，相当于无向图中的56个结点。 根据题目要求我将默认站点与站点之间权值为1。

下面是我使用 i p a d ipad ipad 画出的从西南石油大学出发，前往世纪城的地铁交通路线图。

对于最短路问题，我这里使用 D i j k s t r a Dijkstra Dijkstra 算法来求得从石油大学站到世纪城站的最短路线并使用prev数组记录最短路径并最后输出所选择路线的站点英文名称。

本题实际上可以简化为：

由于疫情原因我们没办法开学啦，为了能让同学们不挂科，心善的老师决定布置大作业作为期末成绩的一部分啦

一个有环无向图中，有n个结点和m条边，每条边的权值都是1，求得从起点s到终点t的最短路长度，并正序输出最短路径信息。

第一行两个正整数，n和m，表示图的结点数和边数。 第二行到n+1行，为n个字符串，代表n个站点信息（中间可能带空格的英文站名） 。 第n+2行到n+2+m行，为三个正整数x，y，z，代表x和y之间连一条权值为z的无向边。

首先输出最短路长度：以及最短路径长度。 然后正序输出最短路径上站点的编号和站名信息。

因此可以将各各站点构造n个点，m条边的数据直接使用 D i j k s t r a Dijkstra Dijkstra 算法即可求得最短路。 D i j k s t r a Dijkstra Dijkstra 算法，经典的最短路算法，基于贪心思想的，适用于非负权值图的时间复杂度为 Θ ( n 2 ) \Theta(n^2) Θ(n2)优秀算法。

由于 D i j k s t r a Dijkstra Dijkstra算法 Θ ( n 2 ) \Theta(n^2) Θ(n2)的算法瓶颈是每次查找dis数组的最小的值，我们可以使用STL中的优先队列优化这一操作，将 Θ ( n ) \Theta(n) Θ(n)的查找优化至 O ( l o g n ) O(logn) O(logn)

但是我作为一名我校优秀的 ACMer 只是使用优先队列怎么行，我决定再进行一些优化（因为优先队列还是太慢啦），考虑如果要优化 D i j k s t r a Dijkstra Dijkstra算法，那么就要摒弃落后的优先队列，由于只需要借用优先队列寻找最小值操作，而优秀的线段树完全可以代替实现。因此我决定补充一个线段树优化版本的 D i j k s t r a Dijkstra Dijkstra。

具体思路如下： D i j k s t r a Dijkstra Dijkstra算法的核心思想就是每次取出最小的 d i s [ i ] , i ϵ [ 1 , n ] dis[i],i\epsilon[1,n] dis[i],iϵ[1,n] 且当前的结点i并未被访问过。因此我们使用线段树来全程模拟这个操作。我们用线段树维护区间最小值。每次取出区间 [ 1 , n ] [1,n] [1,n] 中 d i s dis dis最小的点，作为当前节点。根据 D i j k s t r a Dijkstra Dijkstra的设计思想，当前节点的 d i s dis dis已经是最小的了，所以遍历该点能到达的所有子结点，更新子结点的 d i s dis dis,然后由于普通的线段树不支持删除操作（可持久化线段树支持，这里就不展开了）因此直接在线段树中把当前节点位置的值改成 + ∞ +∞ +∞即可(模拟将该点删除)。

二者的理想时间复杂度虽然相同，都是 Θ ( n l o g m ) \Theta(nlogm) Θ(nlogm)，但是线段树的常数更小，一般运行起来时间会是优先队列的 1 2 \frac{1}{2} 21​！(至于我是怎么得到这个结论的，请看文末)

我这里使用一个 p r e v [ j ] prev[ j ] prev[j]来记录最短路上顶点 j 的前驱，可以在 Θ ( V ) \Theta(V) Θ(V)的时间内完成最短路径的恢复（V是边数）。在 d [ j ] d[ j ] d[j]被 d [ j ] = d [ k ] + c o s t [ k ] [ j ] d[ j ] = d[ k ] + cost[ k ][ j ] d[j]=d[k]+cost[k][j]更新时，修改 p r e v [ j ] = k prev[ j ] = k prev[j]=k，这样就可以求出来 p r e v prev prev的数组，可以在以上算法中用路径前驱标记法来还原出来路径。

为了输出站点名称，我使用56个int型整数代表56个沿途可能经过的站点。使用map来存储站点信息（英文名）。

本次5条路线一共56个站点（结点）

通过百度百科查找成都市地铁信息梳理得到下面我所需要用到的站点列表：

地铁三号线站点信息 结点1~23

起点：石油大学站 Southwest Petroleum University 钟楼站 Clock Tower 马超西路站 Machao Road West 团结新区站 Tuanjiexinqu 锦水河站 Jinshuihe 三河场站 Sanhechang 金华寺东路站 Jinhua Temple Road East 植物园站 Botanical Garden 一期工程 军区总医院站 Chengdu Junqu General Hospital 熊猫大道站 Panda Avenue 动物园站 Chengdu Zoo 昭觉寺南路站 Zhaojuesi Road South 驷马桥站 Simaqiao 李家沱站 Lijiatuo 前锋路站 Qianfeng Road 红星桥站 Hongxing Bridge 市二医院站 Chengdu Second People’s Hospital 春熙路站 Chunxi Road 新南门站 Xinnanmen 磨子桥站 Moziqiao 省体育馆站 Sichuan Gymnasium 衣冠庙站 Yiguanmiao 高升桥站 Gaoshengqiao

地铁一号线站点信息： 结点：24~31

倪家桥站 Nijiaqiao 桐梓林站 Tongzilin 火车南站 South Railway Station 高新站 Hi-Tech Zone 金融城站 Financial City 孵化园站 Incubation Park 锦城广场站 Jincheng Plaza

终点：世纪城站 Century City

地铁一号线站点信息： 结点：32~37

人民北路站 North Renmin Road 文殊院站 Wenshu Monastery 骡马市站 Luomashi 天府广场站 Tianfu Square 锦江宾馆站 Jinjiang Hotel 华西坝站 Huaxiba

地铁二号线站点信息： 结点：38~39

牛王庙站 Niuwangmiao 东门大桥站 Dongmen Bridge

地铁六号线站点信息： 结点：40~46

顺江路站 Shunjiang Road 三官堂站 Sanguantang 东光站 Dongguang 琉璃场站 Liulichang 琉三路站 Liusan Road 金石路站 Jinshi Road 金融城东站 East Financial City

地铁九号线站点信息： 结点：47

心岛站 Xindao

地铁五号线站点信息： 结点：48~56

西北桥站Xibeiqiao 花牌坊站Huapaifang 抚琴站Fuqin 中医大省医院站Chengdu University of TCM &Sichuan Provincial People’s Hospital 青羊宫站Qingyang Taoist Temple 省骨科医院站Sichuan Provincial Orthopaedic Hospital 科园站Keyuan 九兴大道站Jiuxing Avenue 神仙树站Shenxianshu

梳理完56个结点有了这些信息以后就可以建图了！

然后手动造数据： 一共56个结点与结点信息（站名）和60条无向边

最后整张地铁图的数据及最后的测试数据如下：

第一行两个正整数，n和m，表示图的结点数和边数。 第二行到n+1行，为n个字符串，代表n个站点信息（中间可能带空格的英文站名） 。 第n+2行到n+2+m行，为三个正整数x，y，z，代表x和y之间连一条权值为z的无向边。

首先输出最短路长度：以及最短路径长度。 然后正序输出最短路径上站点的编号和站名信息。 样例：