P3238 [HNOI2014] Roadblock

This problem may not have a correct solution; all posted solutions have been hacked.

Country A has $N$ cities, numbered $1$ to $N$. There are $M$ directed roads between these $N$ cities, and the length of each road is a positive integer. The Ministry of Transport of Country A has designated a path from city $1$ to city $N$, and it is guaranteed that this path has the shortest length among all paths from city $1$ to city $N$. Unfortunately, as more and more people travel from city $1$ to city $N$, this designated path often gets congested. Now Country A wants to know, for each road on this path, what the shortest path length from city $1$ to city $N$ would be if that road becomes impassable.

The first line contains three space-separated positive integers $N$, $M$, and $L$, denoting the number of cities, the number of directed roads, and how many roads are on the designated shortest path, respectively. The next $M$ lines each contain three space-separated integers $a$, $b$, and $c$, indicating there is a directed road from city $a$ to city $b$ with length $c$. The line numbers of these $M$ lines are also the corresponding road IDs; that is, the $1$-st of these lines corresponds to road ID $1$, the $2$-nd corresponds to road ID $2$, ..., and the $M$-th corresponds to road ID $M$. The last line contains $L$ space-separated integers $\operatorname{sp}(1), \ldots, \operatorname{sp}(L)$, which in order denote the IDs of the roads on the designated shortest path from city $1$ to city $N$.

Output $L$ lines, each containing one integer. The integer on the $i$-th line ($i = 1, 2, \ldots, L$) is the length of the shortest path from city $1$ to city $N$ after removing the road with ID $\operatorname{sp}(i)$. If there is no path from city $1$ to city $N$ after the removal, output $-1$.

$100\%$ of the testdata satisfies $2 < N < 100000$, $1 < M < 200000$, $c \in [0, 10000] \cap \mathbb{Z}$. Testdata has been strengthened by Vfleaking. Two sets of hack testdata were added on 2023-04-08. Translated by ChatGPT 5