Global firefighters P55713


Statement
 

pdf   zip

thehtml

A new criminal group named Arsenists Without Borders are lighthing fires all over the world with a special chemical composition that makes the fires hard to neutralize. So, in order to protect people, during the last UN reunion it was decided to create a global unit of firefighters. But now they need some nice slogans about how good are the firefighters. Explicitely, they want to advertise how much time it will take them to get to some locations.

Input

Input starts with the number of cases. Every case begins with the number of cities ‍n and the number of roads ‍m. Follow m triples (u, v, d) to indicate a bidirectional road from u to ‍v (with uv) of length d > 0. Afterwards, we have a number k, followed by k different cities where the firefighter units are located. Finally, we have the number of queries q for this case, followed by q numbers of a city (numbered from 0 to n − 1). You can suppose that the map is connected, and that there is at most one single road directly connecting two cities. Assume 0 < n ≤ 105, n−1 ≤ m ≤ 30n, 0 < k ≤ min(n, 1000), and 0 < q ≤ 1000.

Output

For every case, print first its number starting at one. Afterwards, for each query, provide the distance between the city and the closest firefighter unit, and in which city it is located (in case of a tie, print the lowest number). Separate the output for two cases with a blank line.

Public test cases
  • Input

    3
    5 6
    0 1 2    1 2 3    2 3 4
    3 4 5    4 2 9    0 4 11
    2  0 1
    2  3 4
    5 6
    0 1 3    1 2 4    2 3 5
    3 4 6    4 2 10   0 4 15
    2  0 1
    2  3 4
    5 4
    1 0 15   3 2 10   4 1 5    0 2 10
    2  4 3
    1  0
    

    Output

    Case #1
    To get to 3, distance 7, from city 1.
    To get to 4, distance 11, from city 0.
    
    Case #2
    To get to 3, distance 9, from city 1.
    To get to 4, distance 14, from city 1.
    
    Case #3
    To get to 0, distance 20, from city 3.
    
  • Information
    Author
    Francesc Martínez
    Language
    English
    Official solutions
    C++
    User solutions
    C++