P4021 [CTSC2012] 最短路

给定一个节点 $1$ 和节点 $N$ 连通的正权无向图，请你删除不超过 $K$ 条边，使得节点 $1$ 和节点 $N$ 仍然连通的同时，这两点之间的最短路尽可能长 。

**本题为提交答案试题，[输入文件](https://pan.baidu.com/s/1o7K2dCm)（`shortest1.in`~`shortest10.in`）请在链接中下载**。 输入文件 `shortest*.in` 的第一行包含三个正整数 $N,M,K$。其中 $N$ 表示节点数，$M$ 表示边数，节点的编号由 $1$ 至 $N$，边的编号由 $1$ 至 $M$。接下来 $M$ 行， 每行三个正整数 $u,v,w$，表示有一条连接节点 $u$ 和节点 $v$ 的边，权值为 $w$。

输出文件 `shortest*.out` 的第一行包含一个非负整数 $T$，表示需要删掉的边数。 接下来 $T$ 行，每行一个 $1$ 到 $M$ 之间的整数 $x$，表示删掉输入中的第 $x$ 条边。你需要保证这 $T$ 个整数互不相同。

### 样例说明 样例中从节点 $1$ 到 $3$ 的最短路径长度为 $1$，删去第三条边之后，最短路径长度为 $2$。 ### 评分标准 对于每个测试点，设有评分四个参数 $s_1,s_2,s_3,s_4$。假设你的方案的最短路为 $\textit{ans}$。 如果你没有输出，或者输出不合法，或者最短路不存在，得 $0$ 分。 如果最短路存在，得 $1$ 分。 如果 $\textit{ans}\geq s_1$，得 $3$ 分。 如果 $\textit{ans}\geq s_2$，得 $5$ 分。 如果 $\textit{ans}\geq s_3$，得 $8$ 分。 如果 $\textit{ans}=s_4$，得 $10$ 分。 如果 $\textit{ans}>s_4$，得 $12$ 分。 取满足条件的分数中的最高得分为该测试点你的得分。 ### 如何测试你的输出 首先先编译 `checker.cpp`。 在你的目录下有一个名为 `checker` 的程序可以用来检查你的输出，你可以在终端中使用以下命令来检查你的输出： ``` ./checker N ``` 其中 $N$ 为测试点的编号；例如，要测试第 $3$ 个测试点可以使用 ``` ./checker 3 ``` 该程序会检测你的输出方案是否合法。如果方案合法，程序还会给出该方案的最短路的长度值。 ### 特别提示 请妥善保存输入文件和你的输出文件，及时备份，以免误删。