# Els trens de Porto

0.58

Com a cada SWERC, el professor Oak perpetua una tradició que assegura
que algun equip UPC guanyi: menjar un cop a un Burguer King. Hi han
quedat tots a una hora convenida, però el professor hi ha anat
directament, mentre que els tres equips s'han quedat a l'hotel jug\...
d'això, "entrenant fort" fins a l'hora de sortir. Quan, finalment, els
equips han agafat els Ferrocarrils de Màxima Estupidesa (FME) de Porto,
en algun moment s'han equivocat de camí. Alguns dels concursants es
conformen culpant al Rafa fent jocs de paraules ("Dijikstre que el tren
era este!"), però altres intenten arribar a temps en qualsevol cas.

Podeu ajudar els equips UPC? Sembla que ells no saben calcular camins
mínims! Donats els horaris dels trens de la FME, i la posició dels
equips UPC en aquest moment, heu de calcular el temps mínim necessari
per arribar al Burger King.

0.45

::: center
![image](bk.eps){width="5.7cm"}
:::

## Entrada

L'entrada consisteix en diversos casos. Cada cas comença amb el nombre
d'estacions $n$ i el nombre de línies de tren $m$, seguits de la
informació de cada línia: el nombre d'estacions $k_i$, seguit de les
$k_i$ estacions en ordre. Finalment, tenim l'estació $u$ on estan els
equips UPC i l'estació $b$ on es troba el Burger King.

Podeu suposar $2 \le n \le 10^4$, $1 \le m_i \le 1000$,
$2 \le k_i \le 100$, i $u \ne b$. Les estacions es numeren entre 1 i
$n$. Les línies de tren no tenen estacions repetides, van en els dos
sentits, i no són circulars. A cada minut, surt un tren de cada estació
en els dos sentits. Els trens triguen un minut en anar des d'una estació
a la següent. Suposeu que els transbordaments entre línies són
instantanis. Sempre hi ha algun camí entre $u$ i $b$.

## Sortida

Per a cada cas, escriviu el temps mínim per anar de $u$ a $b$.

## Informació del problema

Autoria: Ángel García

Generació: 2026-01-25T11:36:38.333Z

© *Jutge.org*, 2006--2026.\
<https://jutge.org>
