VM7WC '16 #3 Gold - Hello, Officer.

View as PDF
Submit solution
Points: 10
Time limit: 0.6s
Memory limit: 64M
Author:
JeffreyZ
Problem type

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 Kenneth'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 realization 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 be 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. Dhruvit starts screaming. Shahir, still inside the box, practices his promposal. The police officer started chasing them again, sirens blaring, 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≤N≤2000): The number of houses in Shahir's neighbourhood.
  • M (1≤M≤5000): The number of roads in Shahir's neighbourhood.
  • B (1≤B≤N): Shahir's date lives in house B.
  • Q (1≤Q≤N): The number of queries that the program must answer.

The next M lines contain three space-separated integers X, Y, and Z (1≤X,Y≤N,1≤Z≤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≤A≤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

Copy
6 7 6 5
1 2 1
2 3 1
2 5 3
5 1 200
3 4 2000
4 5 3
4 6 1000
1
2
3
4
5

Sample Output

Copy
1007
1006
1007
1000
1003

Warning

Don't code and drive, kids.

Comments


  • 0
    stanwww  commented on Oct. 25, 2024, 2:29 a.m. ← edited

    Never mind. I solved it


  • 1
    rnpmat08_v2  commented on June 14, 2024, 11:41 p.m. ← edited

    Note that it is possible for them to be at the date's house already and that it is guaranteed for only one edge to exist between two nodes


  • 28
    xXxP0t4t0MStRxXx  commented on April 1, 2017, 11:14 p.m. ← edit 3
    • First paragraph: Kenneth's car
    • Third paragraph: This isn't even his car