2746 「CTSC2011」道路监控

道路安全部门最近计划部署从 A 市到 B 市的道路监控系统，以提高该部门对于紧急事件的应对能力。A 市到 B 市的道路网可以描述为一个无向图 $G=(V, E)$，其中 $V$ 表示道路网中的节点集合，$E$ 表示连接节点的双向道路集合。所有的节点由 $1\sim n$ 进行编号，其中 $n$ 为节点个数。A 市所处的节点为 $s$，B 市所处的节点为 $t$。

该部门计划在其中一些道路中安装监控设备，以降低整个道路网的响应难度。当紧急事件发生时，部门需要派遣一些人力到一些道路中进行执勤，以使得任何一条从节点 $s$ 到达节点 $t$ 的路径都经过至少一条监控道路（安装了监控设备或者有人执勤）。因此响应难度定义为需要派遣人力的最少道路数，以使得任何一条从 $s$ 到 $t$ 的路径都经过至少一条监控道路。

由于自然环境不同，在不同的道路安装监控设备的代价也可能不同。具体而言，对于一条边 $e$，其安装设备的代价为 $W(e)$。由于经费有限，他们希望找到一个方案，使得该道路网的响应难度不超过 $k$。请你帮助他们寻找一个尽可能经济的部署方案。

这是一道提交答案的试题，在你的目录下有 $10$ 个输入文件 road*.in。详见附加文件。

输入文件的第一行为三个整数 $n,m$ 和 $k$，分别表示道路网中的节点数、道路数以及响应难度的上限值。

输入文件第二行包含两个整数 $s$ 和 $t$，表示 A 市与 B 市的节点编号。

接下来 $m$ 行，每行三个正整数 $a_i, b_i, w_i$，表示一条连接节点 $a_i$ 和节点 $b_i$ 的道路，其安装监控设备的费用为 $w_i$。

对于每一个输入文件，在目录下给出对应的输出文件 road*.out。

输出文件第一行包含一个值 $s$，表示选手提供的方案中将在 $s$ 条道路上安装监控设备。接下来 $s$ 行每行包含一个整数 $p_i$，表示在输入文件中的第 $p_i$ 条道路上安装监控设备（边从 $1$ 开始编号）。

评分标准

对于每个测试点，如果你没有输出或者输出不合法则得 $0$ 分。

对于每个测试点，我们设有五个评分参数 $m_1, m_2, m_3, m_4$ 和 $m_5$。假设选手的方案中费用为 $c$： - 若 $c \lt m_1$，得 $12$ 分； - 若 $c = m_1$，得 $10$ 分； - 若 $m_1 \lt c \le m_2$，得 $8$ 分； - 若 $m_2 \lt c \le m_3$，得 $5$ 分； - 若 $m_3 \lt c \le m_4$，得 $3$ 分； - 若 $c \lt m_5$，得 $1$ 分； - 否则，得 $0$ 分。

如何测试你的输出

在你的目录下有一个名为 checker 的程序可以用来检查你的输出，在此提供源文件。你可以在终端中编译后使用以下命令来检查你的输出：

./checker N

其中 $N$ 为测试点的编号，例如，要测试第 $3$ 个测试点可以使用

./checker 3

该程序会检测你的输出是否合法。如果方案合法，程序还会给出该方案的部署费用总和。

需要注意的是，你的输出应与输入一同放在 checker 所在目录下。