11360: 边的删减
[Creator : ]
Description
给定一个由 $n$ 个点和 $m$ 条边组成的无向连通加权图。
设点 $1$ 到点 $i$ 的最短路径长度为 $d_i$。
现在,你需要删掉图中的一些边,使得图中最多保留 $k$ 条边。
如果在删边操作全部完成后,点 $1$ 到点 $i$ 的最短路径长度仍为 $d_i$,则称点 $i$ 是一个优秀点。
你的目标是通过合理进行删边操作,使得优秀点的数量尽可能大。
Input
第一行包含三个整数 $n,m,k$。
接下来 $m$ 行,每行包含三个整数 $x,y,w$,表示点 $x$ 和点 $y$ 之间存在一条长度为 $w$ 的边。
保证给定无向连通图无重边和自环。
Output
第一行包含一个整数 $e$,表示保留的边的数量 $(0≤e≤k)$。
第二行包含 $e$ 个不同的 $1\sim m$ 之间的整数,表示所保留的边的编号。
按输入顺序,所有边的编号从 $1$ 到 $m$。
你提供的方案,应使得优秀点的数量尽可能大。
如果答案不唯一,则输出任意满足条件的合理方案均可。
Constraints
对于全部测试点,$2≤n≤10^5,\ 1≤m≤10^5,\ n−1≤m,\ 0≤k≤m,\ 1≤x,y≤n,\ x≠y,\ 1≤w≤10^9$。
Sample 1 Input
3 3 2
1 2 1
3 2 1
1 3 3
Sample 1 Output
2
1 2
Sample 2 Input
4 5 2
4 1 8
2 4 1
2 1 3
3 4 9
3 1 5
Sample 2 Output
2
3 2