题目背景

这是一道提交答案题。

SPJ：zlxFTH

下发数据

题目描述

题目依然是关于 CoH 的世界。由于被门德斯虐待了 $922$ 次，虫虫决定转业……现在虫虫在 CoH 的世界里担任邮递员，他负责把 GM 的信传递到每个玩家手里。同样 CoH 的世界可以看做一个无向图。众所周知，行动需要消耗行动值，所以虫虫希望在消耗的行动值最少的情况下把信送到每个玩家手里。由于 GM 给了虫虫一个迁徙卡，虫虫可以从任意一个玩家开始。他需要经过每个玩家至少一次，但是每条路可以重复行走。他需要你给他一个方案，使他消耗的行动值尽量少。

输入格式

输入文件为 carrier1.in-carrier10.in。

第一个数 $n$ 为玩家数目，以后 $n-1$ 行为地图。这 $n-1$ 行中，第 $i$ 行的第 $j$ 列表示 $i$ 到 $j+i$ 的无向路消耗的行动值。

输出格式

输出文件为 carrier1.out-carrier10.out，分别对应 carrier1.in-carrier10.in。

第一行为消耗的行动值总和，以后的若干行为路线。

一条路线 $\{u_1, u_2,\cdots u_m\}$，表示从 $u_1$ 出发，依次走到 $u_2, u_3,\cdots u_m$，然后结束。你需要每一行依次输出一个 $u$。

样例输入 #1

5
2 2 8 9
3 6 8
1 2
4

样例输出 #1

8
2
1
3
4
3
5

数据范围

对于 $30\%$ 的数据，$n = 10$。

对于另外 $70\%$ 的数据，$n = 100$。

对于 $100\%$ 的数据，边权 $0\le w < 2^{31}$。

评测器使用方法

下发数据中包含了一个叫 checker.cpp 的文件。

使用 g++ -o check checker.cpp -std=c++14 -O2 编译它即可得到一个可执行文件。

你需要把输入文件和你的输出文件拼在一起，在末尾添加一个 $0$。

程序会检查你的路径是否合法，路径长度是否匹配。

如果出错会返回提示信息。

评分方法

如果输出不合法或使评测器崩溃（例如输出长度太太太太太长了），得 $0$ 分。

$ans$ 为你的答案，$std$ 为 zlxFTH 的答案。（答案为消耗的行动值总和）

如果 $ans < std$ 则得 $15$ 分，如果 $ans > 2\times std + 100$ 则得 $1$ 分。

否则得分为 $\max\{0, (\frac{std + 100}{ans + 100} - 0.5)\times 18 + 1\}$。