Each test case starts with a line containing three integers V, E, and Q, denoting the number of vertices, edges, and queries, respectively. Note that vertices are identified with integers from 0 to V-1. E lines follow, each containing three integers s_i, d_i, l_i, denoting the source vertex, destination vertex, and latency; these three integers describe the ith edge. Q lines follow, each containing a single vertex q_i, for which you must determine the total latency T_i of the shortest path from vertex 0 to vertex q.
Our goal in this problem is to determine the “lowest latency routes” starting from your location. The internet in this problem is modeled by a graph, with vertices corresponding to other clients or servers, and edges representing the links between clients/servers. Each edge is not undirected, i.e., the links are unidirectional. At the same time, each link adds a constant latency if you use the link in your routes. Note that if you need to communicate with your own client, then the latency is 0. We represent your location as the vertex 0. Your goal is to determine the total latency it would take if you used the shortest path route from your location to any other client/server in the network.
Input Format
Each test case starts with a line containing three integers V, E, and Q, denoting the number of vertices, edges, and queries, respectively. Note that vertices are identified with integers from 0 to V-1. E lines follow, each containing three integers s_i, d_i, l_i, denoting the source vertex, destination vertex, and latency; these three integers describe the ith edge. Q lines follow, each containing a single vertex q_i, for which you must determine the total latency T_i of the shortest path from vertex 0 to vertex q.
Constraints
2≤V≤100,000
V≤E≤1,000,000
1≤Q≤V
0≤s_i,d_i
Output Format
For each query vertex q_i, you must output a line containing q_i and T_i. If q_i is not reachable, output “None” instead.
Step by step
Solved in 4 steps with 2 images
