FastPrep
Problem · Graph

Directed Graph Shortest Distance

Learn this problem
● MediumAmazon logoAmazonFULLTIMEONSITE INTERVIEW
See Amazon hiring insights

Problem statement

You are given a directed graph with nodes labeled from 0 to n - 1. Each edge is [from, to, weight] and has a nonnegative integer weight.

Return the minimum total weight of a path from source to target. Return -1 when the target is unreachable.

Function

shortestDistance(n: int, edges: int[][], source: int, target: int) → long

Examples

Example 1

n = 5edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]]source = 0target = 4return = 7

The path 0 to 2 to 1 to 3 to 4 has total weight 7.

Example 2

n = 3edges = [[0,1,2]]source = 0target = 2return = -1

No directed path reaches node 2.

Constraints

  • 1 <= n <= 100000
  • 0 <= edges.length <= 200000
  • 0 <= weight <= 10^9
  • Source, target, and edge endpoints are valid node labels.
  • The answer fits in a signed 64-bit integer.

More Amazon problems

drafts saved locally
public long shortestDistance(int n, int[][] edges, int source, int target) {
    // Write your code here.
}
n5
edges[[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]]
source0
target4
expected7
checking account