P4021 [CTSC2012] Shortest Path

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.

This is an output-only problem. Please download the input files from the link: [input files](https://pan.baidu.com/s/1o7K2dCm) (`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$.

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.

### 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