[CTSC2012] 最短路

给定一个节点 1 和节点 N 连通的正权无向图 G，请你删除 不超过 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 ≤ K)，表示需要删掉的边数。 接下来 T 行，每行一个 1 到 M 之间的整数 x，表示删掉输入中的第 x 条边。你需要保证这 T 个整数互不相同。

3 3 1
1 2 1
2 3 1
1 3 1

1
3

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