#3936. 1261. 【例9.5】城市交通网络

1261. 【例9.5】城市交通网络

题目描述

给定 N 个城市组成的有向交通网络,求从 1 号城市到 N 号城市的最少总费用,并输出一条最短路径。道路可以从较大编号通向较小编号,网络也可以含有环。

样例的一条最短路径为 1 → 3 → 5 → 8 → 10,沿途费用分别为 5、6、3、5,总费用为 19。

最省费用所经过的城市序列即为最短路径。

输入格式

第一行为城市数 N(1 ≤ N ≤ 20)。 后面 N 行,每行 N 个非负整数,表示有向道路费用矩阵。矩阵第 i 行第 j 列为正数时,表示从 i 到 j 的一条道路及其费用;为 0 时表示没有道路。保证 N 号城市可从 1 号城市到达。

输出格式

第一行输出最少费用,格式为 minlong=费用;第二行输出路径上的城市编号,以空格分隔。若有多条最短路径,输出其中任意一条即可;不得输出额外内容。
10
0  2  5  1  0  0  0  0  0  0
0  0  0  0 12 14  0  0  0  0
0  0  0  0  6 10  4  0  0  0
0  0  0  0 13 12 11  0  0  0
0  0  0  0  0  0  0  3  9  0
0  0  0  0  0  0  0  6  5  0
0  0  0  0  0  0  0  0 10  0
0  0  0  0  0  0  0  0  0  5
0  0  0  0  0  0  0  0  0  2
0  0  0  0  0  0  0  0  0  0
minlong=19
1 3 5 8 10

来源

一本通在线评测 ybtbas-1261