P9618 Subway

> A second-year student, all alone. > > Looking up at the sky above, the gray city’s dome. > > In this dating room called the universe, > > Maybe we just happened to not meet.

A famous engineering expert, 625OutContradiction, designed a subway transportation network $G$. $G$ has $n$ stations and $m$ subway lines. The $i$-th subway line $P_i$ passes through several stations in the transportation network, in the form $P_i=(u_1,u_2,u_3,\ldots,u_{k_i})(k_i>0)$. Between every two adjacent stations $u_j,u_{j+1}(j

The first line contains three integers $n, m, q$. The next $m$ lines describe the subway lines. The $i$-th line is in the form: $k_i,u_1,u_2,u_3,\ldots,u_{k_i}$, representing one subway line. The next $q$ lines each contain three integers, representing $a,b,c$.

Output $q$ lines, each corresponding to the answer for one question.

### Sample #1 Explanation $1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5$ is the first given subway line. $1\rightarrow 3$ and $2\rightarrow 4\rightarrow 5$ are the second and third subway lines. For the first two queries, there is an optimal travel plan: take the second subway line from station $1$ to station $3$, then transfer at station $3$ to the first subway line to reach the destination. In total, it passes through $3$ subway tracks and makes $1$ transfer, so the answers for the first two queries are $3\times 1+1\times 1=4$ and $3\times 3+1\times 0=9$, respectively. For the third query, since transfers are expensive, the optimal plan is to follow the first subway line all the way to the destination, passing through $4$ subway tracks, so the answer is $4$. ### Constraints For all data: $1\le n \le 10^5$, $1\le m \le 10^4$, $1\le q \le 10^5$, $\sum k_i \le 3\times 10^5$. $0 \le a,b \le 10^6$, $0 \le c \le 20$. --- For $10\%$ of the data: $n \le 20$, $\sum k_i \le 40$, $q \le 30$. --- For another $20\%$ of the data: $c=0$. --- For another $30\%$ of the data: $q=1$. --- There may be subway lines in the problem that pass through only one station. Such lines can be ignored directly. The testdata guarantees that for any query, there exists a valid route that can reach the destination. Translated by ChatGPT 5