P9813 [CCC 2015 S4] Convex Hull

Given an undirected graph with $n$ points and $m$ edges, each edge has two weights $t_{i}$ and $h_{i}$. You need to find a path from $s$ to $t$ such that the sum of $h_{i}$ on the path is $< k$, and the sum of $t_{i}$ is as small as possible. You only need to output this minimum value. If no path satisfying the condition can be found, output $-1$.

The first line contains three integers $k, n, m$. The next $m$ lines each contain four integers $u_{i}, v_{i}, t_{i}, h_{i}$, representing an edge between $u_{i}$ and $v_{i}$, with edge weights $\{t_{i}, h_{i}\}$. The last line contains two integers $s, t$.

If there exists a path satisfying the condition, output one line with one integer, the minimum possible sum of $t_{i}$. Otherwise, output one line with $-1$.

**Constraints:** For $20\%$ of the testdata, $k = 1$, $2 \leq n \leq 200$. For another $20\%$ of the testdata, $k = 1$, $2 \leq n \leq 2 \times 10^{3}$. For $100\%$ of the testdata, $0 \leq h_{i} \leq 200$, $1 \leq t_{i} \leq 10^{5}$, $1 \leq k \leq 200$, $2 \leq n \leq 2 \times 10^{3}$, $1 \leq m \leq 10^{4}$, and $s \neq t$. Translated by ChatGPT 5