DMOPC '14 Contest 6 P6 - Trip - Olympiads Online Judge

DMOPC '14 Contest 6 P6 - Trip

Points: 17 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

Problem type

Toronto is a large city.

With so many bus routes crisscrossing every which way in no coherent fashion, trip planning can quickly become unmanageable. The TTC has a trip-planning app for phones, but it requires a data plan. You, being an excellent programmer with no data plan, have decided to remedy the situation for all the poor data-less souls like you — but mainly you.

You've decided you're going to write an offline trip planner!

Being an expert Google-r, you've found that the TTC provides data dumps of all their routes, so you don't have to ~~enslave~~ hire workers to map out the city for you. There are $S$ $S$ bus stations, numbered $1 \dots S$ $1 \dots S$ , and $R$ $R$ bus routes, numbered $1 \dots R$ $1 \dots R$ . A bus route is represented by a sequence of station ids, and is unidirectional. Each station will have a number of timetables posted — one for each route passing through it — listing the times of arrival of buses for a particular route. Of course, timetables are necessary since buses do not circulate between stations at fixed time intervals. An additional piece of common wisdom is that a route is a first-in-first-out system: the first bus to leave from the start of the route is the first to arrive at the end, with no buses leaving or entering the route midway.

Each timetable will contain a number of entries: the arrival times of buses in minute form ( $1440$ $1440$ minutes in a day). All stations on a route will have the same number of entries into their timetables for that particular route.

If a user of your brilliant app is to leave from station $U$ $U$ at time $T$ $T$ and wishes to arrive at station $V$ $V$ , what is the shortest amount of time they have to spend traveling "The Better Way"? Unfortunately, some routes may be under repair and hence unavailable, so there may not always exist a route from $U$ $U$ to $V$ $V$ . A particularly painful journey may take more than one day.

Input Specification

The first line of input will contain two space-separated integers $S$ $S$ $(2 \le S \le 20)$ $(2 \leq S \leq 20)$ , $R$ $R$ $(1 \le R \le 5)$ $(1 \leq R \leq 5)$ .
The second line will contain three space-separated integers $U$ $U$ , $V$ $V$ $(1 \le U, V \le S)$ $(1 \leq U, V \leq S)$ , $T$ $T$ $(0 \le T < 1\,440)$ $(0 \leq T < 1 440)$ .
For the next $R$ $R$ lines, line $r$ $r$ will start with $S_r$ $S_{r}$ $(2 \le S_r \le 100)$ $(2 \leq S_{r} \leq 100)$ , the number of stations on route $r$ $r$ . The line will then contain $S_r$ $S_{r}$ integers, the station ids on the route. No bus will take longer than a day to traverse the entire route.
The next $Q$ $Q$ lines, where $Q$ $Q$ is the sum of the number of stations on each route ( $Q = \sum_{i=1}^R S_i$ $Q = \sum_{i = 1}^{R} S_{i}$ ) describe timetable data. Each line will begin with an integer $r$ $r$ $(1 \le r \le R)$ $(1 \leq r \leq R)$ followed by an integer $s$ $s$ $(1 \le s \le S)$ $(1 \leq s \leq S)$ and continuing with the integer $T_n$ $T_{n}$ $(1 \le T_n < 100)$ $(1 \leq T_{n} < 100)$ . The rest of the line will contain $T_n$ $T_{n}$ arrival times of buses on route $r$ $r$ arriving at station $s$ $s$ , in minute form. All times in a timetable are unique.

Output Specification

The minimum amount of time the trip will take in minutes, if all routes are chosen optimally. It's possible that it might be impossible to reach the destination using only bus routes. Since you did not have a nice experience with the subway, if this is the case output stay home.

Sample Input 1

Copy

12 2
1 12 0
10 1 2 3 4 5 6 7 8 9 10
3 9 11 12
1 1 1 100
1 2 1 200
1 3 1 300
1 4 1 400
1 5 1 500
1 6 1 600
1 7 1 700
1 8 1 800
1 9 1 900
1 10 1 1000
2 9 1 0
2 11 1 100
2 12 1 0

Sample Output 1

Copy

Explanation for Sample Output 1

The journey takes multiple days.

You must spend $900$ $900$ minutes arriving at station $9$ $9$ . From there, you must transfer to route $2$ $2$ , since route $2$ $2$ is the only route that has station $12$ $12$ on its path. A bus arrives at station $9$ $9$ for route $2$ $2$ at time $0$ $0$ , so we must wait $1440-900=540$ $1440 - 900 = 540$ minutes until a bus arrives. The bus then arrives at station $11$ $11$ at time $100$ $100$ , and then takes another $1440-100$ $1440 - 100$ minutes to arrive at station $12$ $12$ .

Therefore, the total time the journey takes is $900+540+100+1340=2880$ $900 + 540 + 100 + 1340 = 2880$ minutes.

Sample Input 2

Copy

12 1
1 12 0
10 1 2 3 4 5 6 7 8 9 10
1 1 1 100
1 2 1 200
1 3 1 300
1 4 1 400
1 5 1 500
1 6 1 600
1 7 1 700
1 8 1 800
1 9 1 900
1 10 1 1000

Sample Output 2

Copy

stay home

Explanation for Sample Output 2

There is no way to get to station $12$ $12$ , since station $12$ $12$ is not on any given bus route.

Comments

0
Ninjaclasher commented on Nov. 11, 2017, 10:28 p.m. ← edit 3 →
Is it guaranteed that the time it takes to move between two stations on one route is the same on multiple buses? e.g. would this be valid?

Copy
1 1 2 0 100 1 2 2 100 500

3

pyrexshorts commented on May 26, 2015, 11:04 p.m.

E.g. in test case 1, can the first route go to 10, and then come back to 1?

2

kobortor commented on May 26, 2015, 9:30 p.m. ← edit 3 →

Can a bus route visit a station more than once?

Like this

Route paths are labelled from 1 - 5

0

fifiman commented on April 7, 2015, 8:47 p.m.

Can a route start late at night and finish in the morning?

-1

Xyene commented on April 7, 2015, 9:07 p.m.

Yes, it can, and the test data indeed contains such a case.

1

fifiman commented on April 12, 2015, 10:48 p.m. ← edited →

Wait my solution was correct?

9

Xyene commented on April 12, 2015, 11:07 p.m.

Yes. I apologize for how your solution was incorrectly graded during the contest — if there's an error, I was the one to make it.

When preparing the test data for this problem, I had written my own solution to the problem, and used it to generate the output data. Indeed, prior to the contest I was the only one to have solved the problem, since the other contest organizers were busy with their school lives. When skilled competitors began receiving WA verdicts, I manually went over the cases they were failing and solved them by hand to ensure the correctness of the test data.

In the heat of things, I failed to correctly solve the problem by hand (making the same mistake as the aforementioned competitors), and hence was lead to believe my solution (and therefore the test data) was wrong. I then updated the test data to reflect this, effectively giving their incorrect solutions AC and your correct solution WA.

Post-contest, when others began to solve this problem, I found that my original solution was in fact correct. To reflect this, I've increased your rank in the contest so your rating will not be penalized, and have updated the data such that the previous incorrect submissions now fail.

Once again, I'm sorry.

5

fifiman commented on April 12, 2015, 11:42 p.m. ← edit 3 →

"Everybody makes mistakes, everybody has those days." -Hannah Montana

But seriously, its not a big deal. I was just suprised since I rechecked the contest rankings. Thanks for the problem!

EDIT: And the other solutions dont seem to be viewable to me.

0

FatalEagle commented on April 13, 2015, 2:52 p.m. ← edited →

Admin forgot to rescore submissions after changing point values. It's fixed now.