/ StarOI / 题库 /

送外卖

送外卖

描述

仙林校区内开了一家新的轻食店!为了保证运送效率,他们决定雇佣计算机系的同学来送外卖。

仙林校区一共有\(n\)栋宿舍楼(编号\(1\)至\(n\)),宿舍楼之间有道路相连。为了叙述的方便,我们认为轻食店在\(0\)号宿舍楼。从\(i\)号宿舍楼到\(j\)号宿舍楼的最短路线需要骑\(a_{ij}\)分钟的电动车。值得一提的是,某些道路是上坡,某些道路是下坡,所以\(a_{ij}\)并不一定等于\(a_{ji}\)。

你目前在轻食店(0号宿舍楼),电动车上的外卖箱中有一些外卖,你需要规划一条时间最短的路线把外卖送完。由于轻食店的食物很好(jian)吃(fei),所以订外卖的学生老早就在楼下等着了。当你到达一个宿舍楼之后,可以立即把所有该宿舍楼的外卖交付,交付的时间忽略不计。换言之,你送外卖的总用时等于你花在路上的时间之和。送完最后一份外卖后计时立刻停止,返回店铺的时间不计入总用时。

请输出最短的总用时和对应的路线。

输入输出格式

输入

第一行包括一个整数\(n\)。
第二行包括\(n\)个取值为\(0\)或\(1\)的整数。第\(i\)个整数为1表示你的电动车外卖箱中有第\(i\)栋宿舍楼的外卖,反之没有。数据保证本行至少有一个1。
接下来的\(n+1\)行,每行含有\(n+1\)个数,表示\(a_{ij}\)(注意\(i,j\)编号从\(0\)开始)。对于对角线上的元素(即\(a_{ii}\)),数值为零。这些数字在本题中没有意义。

输出

第一行输出一个整数,表示最短的总用时。
第二行输出若干整数(宿舍编号),表示送外卖的顺序。请注意,在本行输出整数的个数,应该等于输入数据的第二行中“\(1\)”的个数。

数据规模与说明

\(1\leq n \leq 16\), \(0\leq a_{ij}\leq 100000\).
如果有多条用时最少的路线,请输出字典序最大的那一条。即在用时最少的情况下,路线中第一个宿舍楼的编号尽可能大;在用时最少且第一个宿舍楼编号一样大的情况下,第二个宿舍楼的编号尽可能大,以此类推。
考虑到部分同学对最短路算法不熟悉,给定的\(a_{ij}\)已经是最短路径了。你不可能通过经由第三个宿舍楼构造出一条用时少于\(a_{ij}\)的路径。换言之,给定的\(a_{ij}\)矩阵满足三角不等式。

输入输出样例

输入

3
1 1 1 
0 7 4 1 
2 0 1 3 
5 4 0 6 
8 6 5 0 

输出

8
3 1 2 

来源

参照CodeVS 2800

信息

难度
9
分类
(无)
标签
(无)
递交数
11
已通过
1
通过率
9%
上传者