她让我完全走投无路。我什么都不懂,我明白这很嚣张,但我从来没有陷入过这样的死胡同。怎么算?条件中的 N - 1 是多少?非常混乱。我不是在寻求解决方案,而是寻求帮助解释。
再次假设有 N 个车站和它们之间的票价表。需要找到所有这样的站点对,在这些站点中,通过某个第三个站点的一次换乘比直接从一个站点到另一个站点更便宜。输入格式
输入格式 在第一行输入一个自然数 N — 站数。其后是 N-1 行,占价格表的一半,与本主题前面的问题一样。输出格式
输出格式 显示满足条件的站号对列表(每对由空格分隔)。对必须按第一个数字升序排序,然后按第二个数字,并且不得重复,包括改变对中数字的顺序。
实际上,如果我们有 3 个站点,那么距离矩阵如下所示
因此,输入线是
解决这个问题,可以使用Dijkstra算法的基本思想。
B
这就是从车站到车站E
(反之亦然)的路径在(随机)价格矩阵中的样子D
。这样一趟的费用是35+3=38。其余的,在我看来,是很明显的。
例如,在这个矩阵中,从站
B
到站的路径E
通过站A
..F
的成本为 75、35、100、38、35、72。最小值为 35,它对应于通过站的路径B
,E
即直接路径,没有中间站。如果需要一个中间站,那么最低费用是38,通过站D
。