P10652 [ROI 2017] Going to the Metropolis (Day 1)

ROI has $n$ cities and $m$ rail lines. Each rail line runs in **one direction**. The $i$-th rail line passes through and stops at cities $v_{i,1}, v_{i,2}, \dots, v_{i,l_i+1}$ in order, where the track length from $v_{i,j} \to v_{i,j+1}$ is $t_{i,j}$. If multiple rail lines pass through city $u$, then you can transfer to another rail line at city $u$. (For each rail line, you may get on or off at any stop.) You need to find a path from city $1$ to city $n$ such that the total length is minimized, and subject to that, the sum of squares of the distances traveled **on trains** between every pair of adjacent **transfer points** along the path is maximized. Note: both the start point and the end point are transfer points. The problem guarantees that a solution exists.

The first line contains two integers $n, m$, meaning there are $n$ cities and $m$ rail lines. The next $m$ lines describe the rail lines. Each line starts with an integer $l_i$ denoting the length of the rail line, followed by $2l_i+1$ integers in the form $v_{i,1}, t_{i,1}, v_{i,2}, \dots, v_{i,l_i}, t_{i,l_i}, v_{i,l_i+1}$, with meanings as described above. It is guaranteed that there are no repeated cities within a single rail line.

Output one line with two integers. The first number is the shortest path length, and the second number is the maximum possible sum of squares.

#### Sample Explanation For sample set #2: Taking line $1$ directly from city $1$ to city $5$ is not the best plan (it cannot achieve the shortest time). The best plan is: > Take line $1$ from city $1$ to city $2$. > > Transfer to line $2$ and ride to city $3$. > > Transfer back to line $1$ and ride to city $5$. In this case, the sum of squares is $3^2 + 1^2 + 5^2 = 35$. For sample set #3: No matter at which station you transfer to line $2$ on the way, the result is the same. The sum of squares is $1^2 + 9^2 = 82$. #### Constraints Note: This problem provides only part of the testdata. For the full testdata, please go to [LOJ P2769](https://loj.ac/p/2769) for judging. For all data: $1 \le m \le 10^6$, $1 \le v_{i,j} \le n$, $1 \le t_{i,j} \le 1000$. Let $sum=\sum l_i$. | Subtask ID | Score | $1 \le n \le $ | $1 \le sum \le $ | Special Property | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $10$ | $20$ | $l_i=1$ | | $2$ | $10$ | $10^3$ | $10^3$ | $l_i=1$ | | $3$ | $17$ | $10^3$ | $10^3$ | None | | $4$ | $17$ | $10^3$ | $10^5$ | None | | $5$ | $19$ | $10^4$ | $2 \times 10^5$ | None | | $6$ | $19$ | $2 \times 10^5$ | $2 \times 10^5$ | None | | $7$ | $8$ | $10^6$ | $10^6$ | None | Translated by ChatGPT 5