ALG-H010HardGraphs
Least-Cost Directed Path
Given n nodes and directed edges [u,v,weight] with nonnegative weights, return the least cost from source to destination, or -1 when unreachable.
Contract
input n: integer
input edges: integer[][]
input source: integer
input destination: integer
return integer
Constraints
- • n >= 1
- • Nonnegative edge weights
- • 0 <= node id < n
Examples
Example 1
n = 4
edges = [[0, 1, 2], [0, 2, 7], [1, 2, 1], [2, 3, 3]]
source = 0
destination = 3
→ 6
Example 2
n = 3
edges = [[0, 1, 4]]
source = 0
destination = 2
→ -1
5 judge tests (2 shown above). Target complexity: O((V+E) log V).