P2483 [Template] k Shortest Paths / [SDOI2010] Magic Pig Academy

Note: For the $k$ shortest paths problem, the A\* algorithm has a worst-case time complexity of $O(nk \log n)$. Although A\* can pass the original testdata of this problem, one can construct cases where A\* fails within the original constraints. In fact, there is an approach using a persistent meldable heap that solves the $k$ shortest paths problem in $O((n+m) \log n + k \log k)$ time. For details, see OI-Wiki: https://oi-wiki.org/graph/kth-path/.

iPig has arrived at the legendary Magic Pig Academy for a two-month training program. After one week of theory and one week of basic magic, iPig has learned a lot about the fundamentals of the pig world: as everyone knows, the world is made of elements; elements can be transformed into one another; energy is conserved $\ldots$ Today iPig is taking a tricky test. From previous learning, iPig already knows many kinds of elements and has learned spells that can transform these elements, each consuming some energy. As a top student from PKU, using the least energy to transform one element into another $\ldots$ well, iPig’s magic instructor isn’t that naive! This time, the instructor has brought many samples of element $1$ and requires iPig to transform them one by one into element $N$ using learned spells. To make it harder, each sample must follow a different conversion process. This seemingly difficult task is actually not a challenge for iPig, because he has a solid backup $\ldots$ you! Note that there can be multiple spells for transforming between two elements, and transformations are one-way. During a conversion, an element (including the starting element) may be visited multiple times, but once the target element is reached, that sample’s conversion process ends. iPig’s total energy is limited, so the maximum number of samples he can convert is finite. See the example for details.

The first line contains three numbers $N, M, E$, representing the number of known elements (numbered from $1$ to $N$), the number of learned spells, and iPig’s total energy. Then follow $M$ lines, each containing three numbers $s_i, t_i, e_i$, indicating a known spell that transforms element $s_i$ to element $t_i$ while consuming energy $e_i$.

Output a single integer: the maximum number of distinct conversion processes that can be completed. The input guarantees that at least one way exists.

There are $4$ meaningful conversion processes: $1\to 4$, consuming energy $1.5$. $1\to 2\to 1\to 4$, consuming energy $4.5$. $1\to 3\to 4$, consuming energy $4.5$. $1\to 2\to 3\to 4$, consuming energy $4.5$. Clearly, at most $3$ of these conversion processes can be completed (choose the first one, and any two of the remaining three), i.e., at most $3$ samples can be converted. If $E=14.9$ is changed to $E=15$, then all of the above processes can be completed, and the answer becomes $4$. # Input Format # Output Format # Hint # Constraints - At least $10\%$ of the total score: $N \leq 6$, $M \leq 15$. - At least $20\%$ of the total score: $N \leq 100$, $M \leq 300$, $E \leq 100$, and $E$ and all $e_i$ are integers (they can be read as integer types directly). - For all testdata: $2 \leq N \leq 5000$, $1 \leq M \leq 200000$, $1 \leq E \leq 10^7$, $1 \leq e_i \leq E$, and $E$ and all $e_i$ are real numbers. # Data Update Log - 2010/xx/xx: Original testdata. - 2018/03/02: @[kczno1](/user/9168) added [a set of testdata](/discuss/35616). - 2018/04/20: @[X_o_r](/user/25188) added [a set of testdata](/discuss/40205). - 2021/01/08: @[LeavingZ](/user/215697) added [two sets of testdata](/discuss/291028). Translated by ChatGPT 5