问题

【题目描述】PTA(数据结构与算法题目集7-9)

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入数据的第 1 行给出 4 个正整数 n、m、s、d，其中：

n（2 ≤ n ≤ 500）是城市的个数，城市的编号为 0~(n−1)；

m 是高速公路的条数；

s 是出发地的城市编号；

d 是目的地的城市编号。

随后的 m 行中，每行给出一条高速公路的信息，分别是：

城市 1、城市 2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过 500。

输入保证解的存在。

输出一行，包含两个整数：

最短路径的长度；

最短路径上收费的总额。如果有若干条路径都是最短的，那么输出最便宜的一条路径。

这是一个典型的带权图的最短路径问题，不仅要计算最短路径的长度，还要在多条最短路径中找到收费最少的路径。为了求解这个问题，可以使用Dijkstra算法，并在计算过程中维护两个信息：

最短路径的长度。

在同样的最短路径长度下，维护最小的收费。

图的表示：用邻接表或邻接矩阵表示城市和高速公路的信息。每条高速公路有两个权值：长度和收费。

Dijkstra算法：使用Dijkstra算法计算从出发地 s 到目的地 d 的最短路径，同时对于每条最短路径，记录其收费情况。

多源最短路径问题：使用Dijkstra算法维护两个数组，一个是到各个城市的最短路径长度，另一个是对应的最小收费。每次更新时，如果发现更短的路径，就更新路径长度和收费。

初始化最短路径为无穷大，起点的最短路径为 0，起点的收费为 0。

使用优先队列（最小堆）来选择当前最短路径的节点，更新其相邻节点的路径和收费。

如果通过某条边可以达到目标节点且是更短的路径，则更新最短路径并且更新收费。如果路径长度相同，则选择收费较少的路径。

使用最小堆（优先队列）来存储当前未处理的城市。每次弹出堆顶的城市，遍历它的邻接城市，更新其最短路径和最小收费。

如果发现通过某条道路到达目标城市 d 的路径更短，或者路径长度相同但收费更少，就更新 dist 和 fee。