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
- 通过率
- ?
- 上传者
相关
在下列训练计划中: