GFSSOC '17 S1 - Path to Waterloo

View as PDF

Submit solution

Points: 8
Time limit: 1.4s
Memory limit: 62M

Authors:
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

Ace is ready to go to Waterloo for the open house. Unfortunately, his parents won't drive him so he has to take some sort of transit there. Ace always starts at home and ends up at Waterloo GO. Along the way, there are N (1 \le N \le 333) stops that Ace can transfer through. Then, there are T (1 \le T \le 999) transfers are given in the form A-B where A is one node and B is the other. The transfer is two directional, meaning Ace can go from A to B or B to A. The names of the transfers will include a dash. Thus, find the minimum number of transfers for Ace to get to Waterloo for the open house. If Ace cannot, print RIP ACE.

Input Specification

First line: N, T, the number of destinations, not including home and Waterloo GO, and the number of transfers.

Next N lines, the name of a transfer.

Next T lines: a transfer, given in the form A-B

Output Specification

The minimum number of transfers to get to Waterloo.

Sample Input 1

2 3
Union Station
MiWay Stop
home-MiWay Stop
MiWay Stop-Union Station
Union Station-Waterloo GO

Sample Output 1

3

Sample Input 2

5 8
China
India
Burma
Uzbekistan
Kyrgyzstan
home-China
China-India
India-Burma
home-Uzbekistan
Uzbekistan-India
Uzbekistan-Kyrgyzstan
Kyrgyzstan-Waterloo GO
Burma-Waterloo GO

Sample Output 2

3

Comments


  • 6
    jimgao  commented on Jan. 20, 2017, 1:19 p.m.

    I think the problem meant "home" instead of "Glenforest" for the starting point. Unless if he lives at Glenforest... That would be kind of sad. :(


    • 0
      tig567899  commented on Jan. 20, 2017, 5:32 p.m.

      The input specifications have been updated we apologize for the inconvenience.


    • 0
      P234rex  commented on Jan. 20, 2017, 4:01 p.m.

      He basically lives at the school but yes, we'll look to editing the problem statement. Apologies for the delayed response.