Problem C
The White Rabbit Pocket Watch
Alice: How can it be?
Rabbit: Trust me Alice. It always takes the same time. When I
go from my home up the road to Queen of Hearts’ Castle, my
watch counts nine hours. However, if I continue down to Mad
Hatter’s House, my watch counts just two hours in total. Isn’t
that great?
Alice: How can it be Rabbit? The path is longer and you take a
shorter time to do it? How can it be?
Rabbit: Trust me Alice! It is all recorded in my logbook. You
can check it. All my trips are there...
Alice: Rabbit, I do not think it can help me...
Rabbit: Alice, no matter where you are, or where you want to
go, or the track you choose, you’ll be able to find how long it
takes you.
Alice: Really?
Rabbit: For sure!
Poor Rabbit, poor Alice.
White Rabbit is helping Alice finding a quick way home through the Rabbit’s hole with his holy logbook of trips. The problem lies in the chronometer of its bizarre pocket watch (it displays the hours from zero to $12$), and the way the Rabbit counts the time with it: If a journey takes $14$ hours (real time), seeing the pointer resting above number one, he assumes it took one hour.
Given that the White Rabbit is telling the truth, can you help Alice finding how long the shortest path home takes, using the Rabbit’s logbook of trips?
Task
Your task is to find the shortest real time it takes for Alice to go from her present location to the Rabbit’s hole. For each trip, the White Rabbit wrote down the trip time, the number of visited locations (not necessarily distinct) and the sequence in which they were visited. That sequence defines the trip because there is at most one direct track between any two locations in the Wonderland and it takes the same time both ways. The White rabbit’s logbook contains trips using all roads in Wonderland; there are no direct connections beyond those implied by the trips in the log book.
Input
The first line contains four integers $N$, $A$, $R$ and $T$, where: $N$ is the number of distinct locations; $A$ identifies the place where Alice is located; $R$ corresponds to the Rabbit’s hole location; and $T$ is the number of trips recorded in White Rabbit’s logbook. All locations are identified by numbers from $1$ to $N$. Each of the next $T$ lines describes a trip logged with format $d \, \, p \, \, a_{1} \, \, a_{2} \, \cdots \, a_{p}$, where $d$ is the trip duration (according to White Rabbit), $p$ is the number of locations and $a_{1} \, \, a_{2} \, \cdots \, a_{p}$ is the sequence of visited locations.
Constraints
|
$2$ |
$\leq $ |
$N$ |
$\leq $ |
$200$ |
Number of locations |
|
$1$ |
$\leq $ |
$T$ |
$\leq $ |
$500$ |
Number of trips in the logbook |
|
$2$ |
$\leq $ |
$p$ |
$\leq $ |
$800$ |
Number of (possibly repeated) locations in a trip |
|
$1$ |
$\leq $ |
$d_{ij}$ |
$\leq $ |
$12$ |
Real time of the direct track between $a_ i$ and $a_ j$ (if it exists) |
|
There are at most $200$ direct tracks. The input will be constructed in such a way that all (real) trip durations are uniquely determined. |
|||||
Output
An integer representing the shortest (real) time it takes for Alice to get home.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 3 3 3 4 1 2 3 2 4 3 1 2 1 1 4 1 2 1 3 |
9 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 5 1 9 0 3 1 2 3 1 4 1 4 2 3 6 4 3 4 1 3 11 5 1 3 4 2 1 4 4 1 2 4 1 6 6 1 2 3 1 4 3 7 4 2 3 4 1 11 3 4 3 5 12 5 5 2 4 2 5 |
6 |
