Hide

Problem C
The White Rabbit Pocket Watch

/problems/whiterabbit/file/statement/en/img-0001.png

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

Please log in to submit a solution to this problem

Log in