DMOPC '14 Contest 7 P6 - Trip

View as PDF

Submit solution


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 S bus stations, numbered 1 \dots S, and R bus routes, numbered 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 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 at time T and wishes to arrive at station 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 to 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 (2 \le S \le 20), R (1 \le R \le 5).
  • The second line will contain three space-separated integers U, V (1 \le U, V \le S), T (0 \le T < 1\,440).
  • For the next R lines, line r will start with S_r (2 \le S_r \le 100), the number of stations on route r. The line will then contain 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 lines, where Q is the sum of the number of stations on each route (Q = \sum_{i=1}^R S_i) describe timetable data. Each line will begin with an integer r (1 \le r \le R) followed by an integer s (1 \le s \le S) and continuing with the integer T_n (1 \le T_n < 100). The rest of the line will contain T_n arrival times of buses on route r arriving at station 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

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

Therefore, the total time the journey takes is 900+540+100+1340=2880 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 12, since station 12 is not on any given bus route.


Comments


  • 0
    Ninjaclasher  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

  • 1
    septence123  commented on April 19, 2017, 10:15 p.m. edit 4

    Nvm


  • 4
    pyrexshorts  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?


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

    Can a bus route visit a station more than once?

    Like this enter image description here

    Route paths are labelled from 1 - 5


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

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


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

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


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

        Wait my solution was correct?


        • 10
          Xyene  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.


          • 5
            fifiman  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.


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

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