Medium · Graphs

Floyd City of Blinding Lights

Given n cities numbered 0 to n − 1, a list of one-way roads [u, v, w] with w ≥ 1, and a list of queries [x, y], return for each query the length of the shortest route from x to y, or −1 if y cannot be reached from x. A city is 0 away from itself, and when a pair has several roads the cheapest one counts.

Examples

Example 1

{
  "n": 4,
  "edges": [
    [0, 1, 3],
    [1, 2, 2],
    [2, 3, 4],
    [0, 2, 8],
    [1, 3, 12],
    [3, 0, 5]
  ],
  "src": 0,
  "dst": 3
}

Output: [9]

Example 2

{
  "n": 4,
  "edges": [
    [0, 1, 5],
    [0, 3, 24],
    [1, 3, 6],
    [2, 3, 4],
    [2, 1, 7]
  ],
  "src": 2,
  "dst": 0
}

Output: [-1]

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.