布线问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description



对于给定的n个元件,设计一个优先队列式分支限界法,计算最佳布线方案,使布线费用达到最小。

Input

输入数据的第一行有1 个正整数n (1≤n≤20)。接下来的n-1 行,每行n-i个数,表示元件i和元件j之间连线数,1≤i< j≤20。

Output

将计算出的最小布线费用以及相应的最佳布线方案输出。

Sample Input

3
2 3
3

Sample Output

10
1 3 2

Hint

请按照题目要求用分支限界法解题。

Source