VM7WC '16 #3 Gold - Hello, Officer.

View as PDF

Submit solution

Points: 10
Time limit: 0.6s
Memory limit: 64M

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

Shahir's promposal's going great! Kenneth, another friend, pulls up to Shahir's house. Dhruvit assumes his mailman costume, and Shahir (taped inside the package) is put into the trunk of Kenneths's car. Why is Shahir put into the trunk of the car? It would be awkward if he got into the box at his date's house while she watched. It would be much more romantic if his date saw Dhruvit pulling the box from the trunk of the car, like a real delivery!

The two start driving to Shahir's date's house, through Shahir's neighbourhood: N houses with M roads, each road connecting two houses. Since this is a free country, Kenneth can drive in both directions on any road. However, Kenneth is a speed demon, and goes somewhere between 20 to 100 km/h on the residential roads between Shahir's house and his date's. This country isn't free enough apparently: all of a sudden, he hears a police siren, and is forced to stop at the side of a road. In his rearview mirror he watches a Crown Vic pull up from behind. A police officer steps out and starts walking towards the car (presumably to give him a ticket for speeding).

Shahir, devoid of any senses and stuck within a cardboard box (which is in turn stuck within the trunk of the car), knows nothing: he's assuming that Kenneth's at a red light. However, Dhruvit just made the sudden realisation that Kenneth doesn't have his G2 Driver's License. Nor his G1. This isn't even his car. And, if the police officer were to open the trunk of the car, he would find a kidnapped minor tied up and stuffed into a cardboard box.

It would easier to just run. While the officer was halfway between the two cars, Kenneth slammed on the pedal, going 0 to 60, and started racing down the roads at. Dhruvit starts screaming. Shahir, still inside the box, practices his promposal. The police officer started chasing them again, sirens ablazing, but that didn't matter. What mattered was getting Shahir to his date's house and his promposal. The only problem was, Kenneth didn't know where he was!

While still driving, Dhruvit took out his laptop and made some edits to the program from the last problem. He still has the map of Shahir's neighbourhood — N houses with M roads — but now he had to find the shortest distance to Shahir's date's house, house B, from any other house in the neighbourhood. He quickly updates the program with the distances of each road, and makes the program such that it's able to find the shortest distance to house B for multiple queries, each query as one of the houses that the trio might be. You should do the same with your program.

Input Specification

On the first line will be four space separated integers:

  • N (1 \leq N \leq 2000): The number of houses in Shahir's neighbourhood.
  • M (1 \leq M \leq 5000): The number of roads in Shahir's neighbourhood.
  • B (1 \leq B \leq N): Shahir's date lives in house B.
  • Q (1 \leq Q \leq N): The number of queries that the program must answer.

The next M lines contain three space-separated integers X, Y, and Z (1 \leq X, Y \leq N, 1 \leq Z \leq 2000), denoting a road that connects house X with house Y that takes Z seconds to transverse.

The next Q lines each contain a query: one integer, A (1 \leq A \leq N), the house that the trio might be at.

Output Specification

For each query and on each line, print the shortest distance to Shahir's date's house from the house specified in the query. If you cannot reach Shahir's date's house from the query house, print -1.

Sample Input

6 7 6 5
1 2 1
2 3 1
2 5 3
5 1 200
3 4 5000
4 5 3
4 6 1000

Sample Output



Don't code and drive, kids.


  • 1
    ZippIE  commented on Dec. 1, 2017, 9:16 p.m. edited

    Edit: After some thinking, I realized that my algorithm isn't optimal. The time limit is actually fine.

  • 5
    P234rex  commented on April 27, 2017, 5:17 p.m.

    The Z value in line 6 of the sample input seems to exceed the constraints.

    • 0
      31501357  commented on March 24, 2019, 12:51 a.m.

      You are right it does but I don't think any of the actual test cases do.

  • 11
    xXxP0t4t0MStRxXx  commented on April 1, 2017, 7:14 p.m. edit 2
    • First paragraph: Kenneths's car
    • Third paragraph: This isn't even his car

  • 0
    moladan123  commented on Jan. 21, 2016, 10:03 p.m.

    (presumably to give him a ticked for speeding).

    Its in paragraph 2 (you're welcome ;)

    • 1
      d  commented on Jan. 21, 2016, 10:05 p.m.

      Input Specification On the first line will be three space separated integers:

      Might as well point this out.

      • 1
        cheesecake  commented on Jan. 21, 2016, 10:12 p.m.

        Fixed and fixed.