Description

Given an undirected graph with positive edge weights in which node $1$ and node $N$ are connected, delete at most $K$ edges so that nodes $1$ and $N$ remain connected, while making the shortest path between them as long as possible.

Input Format

This is an output-only problem. Please download the input files from the link: input files (shortest1.in ~ shortest10.in).

The first line of the input file shortest*.in contains three positive integers $N, M, K$. Here $N$ is the number of nodes, $M$ is the number of edges. Nodes are numbered from $1$ to $N$, and edges are numbered from $1$ to $M$ in input order.
Then follow $M$ lines.
Each line contains three positive integers $u, v, w$, indicating an edge between nodes $u$ and $v$ with weight $w$.

Output Format

The first line of the output file shortest*.out contains a non-negative integer $T$, the number of edges to delete.
Then output $T$ lines, each containing an integer $x$ between $1$ and $M$, indicating that the $x$-th edge in the input is deleted. These $T$ integers must be pairwise distinct.

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

1
3

Hint

Sample Explanation

In the sample, the shortest path length from node $1$ to $3$ is $1$. After deleting the third edge, the shortest path length becomes $2$.

Scoring

For each test point, there are four scoring parameters $s_1, s_2, s_3, s_4$. Let your solution’s shortest path be $\textit{ans}$.

• If you produce no output, or the output is invalid, or the shortest path does not exist, you get $0$ points.
• If a shortest path exists, you get $1$ point.
• If $\textit{ans}\geq s_1$, you get $3$ points.
• If $\textit{ans}\geq s_2$, you get $5$ points.
• If $\textit{ans}\geq s_3$, you get $8$ points.
• If $\textit{ans}=s_4$, you get $10$ points.
• If $\textit{ans}>s_4$, you get $12$ points.

Your score for a test point is the maximum among the applicable cases above.

How to Test Your Output

First, compile checker.cpp.

There will be a program named checker in your directory that can be used to verify your output. You can run the following command in the terminal:

./checker N

Here $N$ is the test point index. For example, to test the $3$-rd test point:

./checker 3

This program checks whether your output solution is valid. If it is valid, it will also report the length of the shortest path.

Special Notes

Please keep your input files and output files properly saved and back them up in time to avoid accidental deletion.

Translated by ChatGPT 5