Dijkstra's Algorithm Test

View as PDF
Submit solution
Points: 10
Time limit: 2.0s
Java 8 5.0s
PyPy 3 4.0s
Memory limit: 128M
Java 8 64M
PyPy 3 192M
Author:
David
Problem type

Dijkstra's algorithm is capable of finding the shortest distance needed to reach any given node on a weighted graph from a starting position. Given a weighted graph, find the minimum distance needed to reach a series of nodes.

Input Specification

The first line of input is n (2 \le n \le 10^5) representing the number of nodes in the graph. They are numbered 0 to n - 1.
The next line of input is m (n - 1 \le m \le 5n) representing the number of edges in the graph.
The next m lines each contain 3 space separated integers, m_1, m_2, m_3 representing a connection between m_1 and m_2 of weight m_3.
The next line is q (1 \le q \le 1000) representing the number of queries about the graph that must be answered.
The next q lines contains a node q_i (1 \le q_i < n) representing a query for the minimum distance to q_i.

Output Specification

For each query and in order, print on a new line the minimum distance needed to reach node q_i from node 0. If it is impossible to reach q_i, print -1.
Note: For Java use of Scanner may cause passable solutions to TLE. Faster input reading is recommended.

Sample Input

7
10
0 3 5
1 2 10
2 4 25
2 3 38
3 4 27
1 5 18
5 0 7
6 1 11
1 4 9
4 0 6
2
6
2

Sample Output

26
25

Comments


  • 0
    jsumabat  commented on Nov. 8, 2019, 12:17 p.m.

    What are the constraints of m_3?


    • 1
      David  commented on Nov. 8, 2019, 4:39 p.m.

      Between 1 and 1000 inclusive