Kattis needs to get somewhere as soon as possible. However, she also wants that the path that she takes to be safe too. She deems that paths that use not more than $\textbf{k}$ junctions to be safe paths. Given a map containing $\textbf{V}$ junctions with weighted edges denoting the time (in minutes) needed to traverse between junctions, a start junction $\textbf{s}$, a destination junction $\textbf{t}$, and a limit of number of junctions $\textbf{k}$, return the minimum amount of time that Kattis needs to go from $\textbf{s}$ to $\textbf{t}$, using at most $\textbf{k}$ junctions (inclusive of $\textbf{s}$ and $\textbf{t}$).
Input starts with an integer $TC\: (1 \le TC \le 10)$, denoting number of test cases.
Each test case starts with a newline. The second line
contains an integer denoting the number of junctions
$V\: (2 \le V \le 1\,
000)$. Then followed by $V$ lines. Each of these lines starts
with an integer $X$
denoting the number of edges from that junction, followed by
$X$ pairs of integers
“vertex weight”
($0 \le $ vertex $ <
V$ and $0 \le $
weight $
\le 10^{5}$). The total number of edges will not exceed
$400\, 000$. Afterwards,
an integer denoting the number of queries $Q\: (1 \le Q \le 20)$ will be given.
Each query is of the format “$s$ $t$ $k$”, $(0 \le s,\: t < V)$, $(1 \le k \le \min (V,\: 30))$, where
all of $s, t, k$ are
integers.
For each query, print the required answer in one line. If the is no answer, print “$-1$”.
Please separate the output of two test cases with a single line.
The sample test case $1$ can be visualized as follows:
Query$(0, 3, 4)$: If Kattis’s current
position is at vertex $\textbf{s}$ = $0$, and the destination is at vertex
$\textbf{t}$ =
$3$, and Kattis can use up
to $\textbf{k}$ =
$4$ junctions, then the
quickest way is this path: $0
\rightarrow 1 \rightarrow 2 \rightarrow 3$ with total
estimated traveling time of: $2+3+7 = 12$ minutes.
However if we have Query$(0, 3, 3)$, then path: $0 \rightarrow 1 \rightarrow 2 \rightarrow 3$ shown earlier is invalid as it uses $4$ junctions as this time Kattis can only use up to $\textbf{k}$ = $3$ junctions. The valid shortest path from $\textbf{s}$ = $0$ to $\textbf{t}$ = $3$ that uses no more than $\textbf{k}$ = $3$ junctions is path: $0 \rightarrow 3$ with total estimated traveling time of: $15$ minutes. This path is $3$ minutes longer than the true shortest path without Kattis’s restriction of not crossing more than $\textbf{k}$ junctions but it is now the correct solution.
The answer for Query$(0, 3, 2)$ is also $15$ minutes.
$\textbf{(30 points)}$: The maps will be undirected weighted trees, $1 \le TC \le 10$, $1 \le V \le 30$, $1 \le Q \le 10$, $K\: =\: V$
$\textbf{(30 points)}$: The maps will be directed graphs, $1 \le TC \le 10$, $1 \le V \le 30$, $1 \le E \le 1\, 500$, $1 \le Q \le 10$, $K\: =\: V$
$\textbf{(40 points)}$: $1 \le TC \le 10$, $1 \le V \le 1\, 000$, $1 \le E \le 200\, 000$, $1 \le Q \le 20$, $K\: =\: \min (V,\: 30)$
Sample Input 1 | Sample Output 1 |
---|---|
2 4 3 1 2 2 9 3 15 1 2 3 2 0 1 3 7 0 2 0 3 4 0 3 3 4 3 1 2 2 9 3 15 1 2 3 2 0 1 3 7 0 1 0 3 2 |
12 15 15 |