We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Floyd : City of Blinding Lights

Floyd : City of Blinding Lights

Problem
Submissions
Leaderboard
Discussions
Editorial

Given a directed weighted graph where weight indicates distance, for each query, determine the length of the shortest path between nodes. There may be many queries, so efficiency counts.

For example, your graph consists of nodes as in the following:

image

A few queries are from node to node , node to node , and node to node .

  1. There are two paths from to :

    • at a distance of
    • at a distance of
      In this case we choose path .
  2. There is no path from to , so we return .

  3. There is one path from to :

    • at a distance of .

Input Format

The first line has two integers and , the number of nodes and the number of edges in the graph.
Each of the next lines contains three space-separated integers and , the two nodes between which the directed edge exists, and , the length of the edge.
The next line contains a single integer , the number of queries.
Each of the next lines contains two space-separated integers and , denoting the start and end nodes for traversal.

Constraints






The distance from a node to itself is always and it is always reachable from itself.

If there are edges between the same pair of nodes with different weights, the last one (most recent) is to be considered as the only edge between them.

Output Format

Print lines, each containing a single integer specifying the shortest distance for the query.

If the destination node is not reachable, return .

Sample Input

STDIN   Function
-----   --------
4 5     n = 4, m = 5
1 2 5   u = 1, v = 2, w = 5
1 4 24  u = 1, v =4, w = 24 ...
2 4 6
3 4 4
3 2 7
3       q = 3
1 2     query 0: from 1 to 2
3 1     query 1: from 3 to 1
1 4     query 2: from 1 to 4

Sample Output

5
-1
11

Explanation

The graph given in the test case is:

image

The shortest paths for the 3 queries are :

  • : The direct path is shortest with weight 5
  • : There is no way of reaching node 1 from node 3
  • : The indirect path is shortest with weight (5+6) = 11 units. The direct path is longer with 24 units length.

Author

pranav9413

Difficulty

Hard

Max Score

75

Submitted By

9571

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature