10170: SPOJ ADATRIP - Ada and Trip
[Creator : ]
Description
Ada the Ladybug loves trips. She travels around world taking photos and souvenirs. This week she went to Buganda. Common Tourist would surely travel around main city and some conurbations, but Ada has different politics. She wants to go as far as possible (because photos from outlying places are much more valuable).
Problem is, that Buganda is very large so she can barely guess such places. Luckily, you are around so she asked you for help. Can you tell her, how far and how many cities are most distant (if the shortest path is used)?
Problem is, that Buganda is very large so she can barely guess such places. Luckily, you are around so she asked you for help. Can you tell her, how far and how many cities are most distant (if the shortest path is used)?
Input
The first line will contain three integers $N,M\ (1 ≤ N ≤ 5*10^5,\ 0 ≤ M ≤ 10^6),\ Q$, the number of cities in Buganda, the number of roads and number of queries (possible arrival cities).
Then $M$ lines follow, with three integers $A,B\ (0 ≤ A, B < N),\ L\ (0 ≤ L ≤ 10), A, B$ are cities, which the (bidirectional) road connects and L is length of the road.
Afterward, $Q$ lines follow, each with number $0 ≤ q_i < N$, meaning the city of arrival.
You are assured that max(N,M)*Q will be always lesser/equal than $10^7$
Gentle warning: Since we are in real world and not in some "graph theory", multiedges and self-edges are completely valid!
Then $M$ lines follow, with three integers $A,B\ (0 ≤ A, B < N),\ L\ (0 ≤ L ≤ 10), A, B$ are cities, which the (bidirectional) road connects and L is length of the road.
Afterward, $Q$ lines follow, each with number $0 ≤ q_i < N$, meaning the city of arrival.
You are assured that max(N,M)*Q will be always lesser/equal than $10^7$
Gentle warning: Since we are in real world and not in some "graph theory", multiedges and self-edges are completely valid!
Output
For each query print two numbers: The distance of most distant place(s) and number of such places.
Sample 1 Input
10 10 10
1 1 1
1 2 1
1 2 3
3 1 1
5 4 10
8 5 10
5 6 5
6 7 3
6 9 3
9 7 4
0
1
2
3
4
5
6
7
8
9
Sample 1 Output
0 1
1 2
2 1
2 1
20 1
10 2
15 2
18 2
20 1
18 2