P9735 [COCI 2022/2023 #2] Tramvaji

Patrik and Josip are riding a tram. They ride for a total of $n$ stops. At every stop after the boarding stop, exactly one of the following events happens upon arrival: - Patrik says: $t$ minutes have passed since we boarded. - Josip says: It took $t$ minutes to get here from stop $y$. Now, based on this information, find which two stops have the shortest travel time between them, and output that time.

The input has $n$ lines. The first line contains an integer $n$ ($2\le n\le1000$), the number of stops. The next $n-1$ lines describe the event that happened at stop $i+1$ on line $i$: - Type 1: $\texttt{Patrik } t_i$ ($1\le t_i\le10^9$). - Type 2: $\texttt{Josip } y_i\texttt{ }t_i$ ($y_i < i + 1$, $1\le t_i\le10^9$). **Each stop is at a different position.**

Output one line with three integers $t$, $x_1$, $x_2$, representing the shortest time, and the start and end stops that achieve this shortest time. **If there are multiple answers, output the lexicographically smallest one.**

**This problem uses bundled testdata.** |$\text{Subtask}$|Score|Special properties| |:-:|:-:|:-:| |$1$|$12$|$t_i \le 1000$ | |$2$|$13$|Only $\texttt{Patrik}$ events | |$3$|$25$|None | **The full score for this problem is $50$ points.** Translated by ChatGPT 5