## DMOPC '14 Contest 7 P6 - Trip

View as PDF

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 bus stations, numbered , and bus routes, numbered . 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 ( 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 at time and wishes to arrive at station , 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 to . A particularly painful journey may take more than one day.

#### Input Specification

• The first line of input will contain two space-separated integers , .
• The second line will contain three space-separated integers , , .
• For the next lines, line will start with , the number of stations on route . The line will then contain integers, the station ids on the route. No bus will take longer than a day to traverse the entire route.
• The next lines, where is the sum of the number of stations on each route () describe timetable data. Each line will begin with an integer followed by an integer and continuing with the integer . The rest of the line will contain arrival times of buses on route arriving at station , 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

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

2880

#### Explanation

The journey takes multiple days.

You must spend minutes arriving at station . From there, you must transfer to route , since route is the only route that has station on its path. A bus arrives at station for route at time , so we must wait minutes until a bus arrives. The bus then arrives at station at time , and then takes another minutes to arrive at station .

Therefore, the total time the journey takes is minutes.

#### Sample Output 2

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

stay home

#### Explanation

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

• commented on Nov. 11, 2017, 5: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?

1 1 2 0 100
1 2 2 100 500
• commented on April 19, 2017, 10:15 p.m. edit 4

Nvm

• commented on May 26, 2015, 7:04 p.m.

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

• commented on May 26, 2015, 5:30 p.m. edited

Can a bus route visit a station more than once?

Like this

Route paths are labelled from 1 - 5

• commented on April 7, 2015, 4:47 p.m.

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

• commented on April 7, 2015, 5:07 p.m.

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

• commented on April 12, 2015, 6:48 p.m. edited

Wait my solution was correct?

• commented on April 12, 2015, 7: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.

• commented on April 12, 2015, 7: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.

• commented on April 13, 2015, 10:52 a.m. edited

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