ADATRIP - Ada and Trip

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)?

Input

The first line will contain three integers 1 ≤ N ≤ 5*105, 0 ≤ M ≤ 106, 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 0 ≤ A, B < N, 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 ≤ qi < N, meaning the city of arrival.

You are assured that max(N,M)*Q will be always lesser/equal than 107

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.

Example 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

Example Output

0 1
1 2
2 1
2 1
20 1
10 2
15 2
18 2
20 1
18 2

Most distant cities (explanation)

0
2 3
3
2
8
4 8
4 8
4 8
4
4 8

Added by:Morass
Date:2017-02-09
Time limit:5.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2023-03-13 16:20:19
1 : don't use "SET" here it will give you TLE
2: store query for future use
3: Normal Djikstras will give you result
2021-12-07 14:50:01
I tried both with Dijkstra and Dial, while storing the values for every query and printing the stored values, when the query repeats, but I´m geeting TLE for both. I´m realy clueless here. Also I´m confuse that the time limit is 5.5 s, but in the ranking the best solution has a time of over 7 s.


Last edit: 2021-12-09 14:38:12
2021-12-06 20:23:04
Submitted with dijkstra Q times. WA at 15th case. Don't know why

Last edit: 2021-12-06 20:23:26
2021-09-01 17:44:35
TLE with sets and AC with Priority Queue.
2021-05-21 10:20:56
if getting WA of test 15 then , check if all distances are infinite then print 0 1;
if getting TLE avoid using map for frequency of distances
try storing answer for each query and if query repeats then just print the stored value

Last edit: 2021-05-21 10:24:03
2021-05-08 18:37:51
STORE THE ANSWER FOR EVERY INDEX IF QUERY REPEATS PRINT THAT , THIS WILL SOLVE TLE ON 15TH TEST CASE
2021-03-25 09:43:37
Time Limit is 5.5s but my accepted solution took 39.54s?What's I am missing?
2021-03-24 05:07:15
SPOJ does not show which testcase you passed and which ones you failed. If it gives WA after running till 15 the WA could have occurred anywhere.
2021-02-11 18:17:22
i am new to graphs i am not getting this?
2021-02-03 10:05:42
No need of Dial's Algorithm, use Dijkstra implemented using heaps. Getting AC.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.