题目描述

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

输入格式

本题为提交答案试题，输入文件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，及时备份，以免误删。