FastPrepFastPrep
Problem Brief

Shortest Paths to Multiple Targets

FULLTIMEPHONE 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.

1Example 1

Input
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]
Output
[3, 4, 4]
Explanation

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

2Example 2

Input
n = 4, edges = [[1, 2, 5]], source = 1, targets = [2, 3]
Output
[5, -1]
Explanation

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

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= n <= 2 * 10^5
  • 0 <= edges.length <= 3 * 10^5
  • 0 <= w <= 10^9
  • Multiple edges and self-loops are allowed.
public long[] shortestPathsToTargets(int n, int[][] edges, int source, int[] targets) {
    // write your code here
}
Input

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]

Output

[3, 4, 4]

Sign in to submit your solution.