P2832 Hard Road [Suspected standard solution (std) complexity is incorrect]

Xiao X came to the mountains and enjoyed the pleasures of the forest. While he was happily forgetting his worries, he suddenly realized that the new semester was imminent.

There are $n$ mountains in the mountainous area. There are $m$ narrow mountain paths between the mountains. Each path connects two mountains, is one-way, and costs Xiao X a certain amount of time. Xiao X is currently at mountain $1$. His goal is mountain $n$, because there is a train station there. However, Xiao X’s stamina is limited. Each time he traverses a narrow mountain path, he becomes more tired, causing the time to traverse any narrow mountain path to increase by $1$.

The first line contains two integers, $n, m$. From line $2$ to line $m+1$, each line contains $3$ integers $A, B, C$, indicating that there is a narrow mountain path from $A$ to $B$ that allows Xiao X to move from $A$ to $B$ with a time cost of $C$.

The first line contains an integer $T$, the shortest time Xiao X needs. The second line contains a sequence of integers separated by spaces, representing Xiao X’s route. For example, [1, 4, 2, 5] means Xiao X starts from mountain 1, moves to mountain 4, then to mountain 2, and finally to mountain 5.

Constraints For all testdata, $n \le 10^4$, $m \le 2 \times 10^5$. The testdata guarantees that the shortest path is unique. Translated by ChatGPT 5