← 返回题目列表

Codeforces · 1076/D

D. 边缘删除

中文机器翻译题面 查看原题

给你一个无向连通加权图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。我们将从顶点 $$$1$$$ 到顶点 $$$i$$$ 的最短路径的长度表示为 $$$d_i$$$。

您必须擦除图形的一些边,以便最多保留 $$$k$$$ 边。如果在删除边之后仍然存在从 $$$1$$$ 到 $$$i$$$ 且长度为 $$$d_i$$$ 的路径,我们称顶点 $$$i$$$ 为好。

您的目标是以最大化好顶点数量的方式擦除边缘。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$1 \le m \le 3 \cdot 10^5$$$, $$$n - 1 \le m$$$, $$$0 \le k \le m$$$) —分别是图中的顶点数和边数,以及图中可以保留的最大边数。

接下来是 $$$m$$$ 行,每行包含三个整数 $$$x$$$、$$$y$$$、$$$w$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$, $$$1 \le w \le 10^9$$$),表示连接顶点 $$$x$$$ 和$$$y$$$ 且重量为$$$w$$$。

给定的图是连通的(任何顶点都可以从任何其他顶点到达)并且简单(没有自环,并且对于每对无序顶点,最多存在一条连接这些顶点的边)。

输出

在第一行打印 $$$e$$$ — 图中应保留的边数 ($$$0 \le e \le k$$$)。

在第二行中打印 $$$e$$$ 从 $$$1$$$ 到 $$$m$$$ 的不同整数 - 应保留在图中的边的索引。边的编号顺序与输入中给出的顺序相同。好的顶点数量应该尽可能多。

示例

输入 #1

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

输出 #1

2
1 2

输入 #2

4 5 2
4 1 8
2 4 1
2 1 3
3 4 9
3 1 5

输出 #2

2
3 2