#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 0minlong=19
1 3 5 8 10