ACOI-11月月赛 T2 旅行

ACOI-11月月赛 T2 旅行

暂无测试数据。

题目背景

\(\sf\orange{huangjunqi}\) 很爱旅行,可是没钱了。这一次,Ta要找一条最短的路去旅行。请你帮帮Ta。

题目描述

\(\sf\orange{huangjunqi}\) 要去 \(n\) 个城市旅行。每两个城市之间都有路,长度为 \(w_{i,j}\)。

\(\sf\orange{huangjunqi}\) 现在在城市 \(1\)。Ta要走完所有城市并回到城市 \(1\)。你要告诉Ta最短的路径长度和走法。

输入格式

输入 \(n\),接下来有一个 \(n \times n\) 的矩阵。第 \(i\) 行第 \(j\) 列表示 \(w_{i,j}\)。

输出格式

一个数 \(s\),表示总路径长度。

第二行表示路径,每个数用 ‘->’ 相连

样例 #1

样例输入 #1

5
0 83 93 36 28
83 0 33 15 68
93 33 0 95 68
36 15 95 0 31
28 68 68 31 0

样例输出 #1

180
1->4->2->3->5->1

样例 #2

样例输入 #2

6
0 44 97 45 81 31
44 0 42 20 89 7
97 42 0 5 18 19
45 20 5 0 35 56
81 89 18 35 0 4
31 7 19 56 4 0

样例输出 #2

122
1->2->4->3->5->6->1

提示

对于所有数据有:\(n\le10,w_{i,j}\le10^4\)。\
本题采用全捆绑,请小心!

信息

ID
1042
难度
(无)
分类
(无)
标签
(无)
递交数
0
已通过
0
通过率
?
上传者

相关

在下列训练计划中:

“你今天AC了吗”团队原创