FastPrep
Problem · Graph

Shortest Paths to Multiple Targets

● MediumWaymoFULLTIMEPHONE SCREEN

You are given a directed weighted graph with n nodes labeled 1 through n. Each edge is represented as [u, v, w], meaning there is an edge from u to v with non-negative weight w.

Also given are a source node source and a list of target nodes targets. Compute the shortest distance from source to each target in order. If a target is unreachable, return -1 for that target.

Function Description

Complete the function shortestPathsToTargets in the editor below.

shortestPathsToTargets has the following parameters:

  1. int n: the number of nodes
  2. int[][] edges: directed edges [u, v, w]
  3. int source: the source node
  4. int[] targets: the targets to query

Returns

long[]: shortest distances to the targets in the same order.

Examples
01 · Example 1
n = 5
edges = [[1, 2, 2], [1, 3, 5], [2, 3, 1], [2, 4, 2], [3, 5, 1], [4, 5, 2]]
source = 1
targets = [3, 4, 5]
return = [3, 4, 4]

Running Dijkstra from node 1 gives distances 3, 4, and 4 to targets 3, 4, and 5.

02 · Example 2
n = 4
edges = [[1, 2, 5]]
source = 1
targets = [2, 3]
return = [5, -1]

Node 2 is reachable with cost 5, while node 3 is unreachable.

Constraints
  • 1 <= n <= 2 * 10^5
  • 0 <= edges.length <= 3 * 10^5
  • 0 <= w <= 10^9
  • Multiple edges and self-loops are allowed.
More Waymo problems
drafts saved locally
public long[] shortestPathsToTargets(int n, int[][] edges, int source, int[] targets) {
    // write your code here
}
n5
edges[[1, 2, 2], [1, 3, 5], [2, 3, 1], [2, 4, 2], [3, 5, 1], [4, 5, 2]]
source1
targets[3, 4, 5]
expected[3, 4, 4]
sign in to submit