How should I practice Shortest Paths in a Nonnegative Directed Graph?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Nation with NaMo phone screen problems in FastPrep.

Is Shortest Paths in a Nonnegative Directed Graph associated with Nation with NaMo?

FastPrep tags this as a Nation with NaMo phone screen coding practice problem when the problem catalog has that company and stage context.

Shortest Paths in a Nonnegative Directed Graph

Nation with NaMo● MediumFULLTIMEPHONE SCREEN

Problem statement

A directed graph has vertices numbered from 0 through n - 1. Each row of edges is [from, to, weight], representing an edge from from to to with a nonnegative cost. Parallel edges, self-loops, and cycles are allowed. For this practice version, use at most 3750 vertices and 5000 edges.

Given a starting vertex source, return an array of length n. Its entry for each vertex is the minimum total cost of a directed path from source to that vertex, or -1 if the vertex cannot be reached. The distance from source to itself is 0, using the empty path.

Function

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

Examples

Example 1

n = 5edges = [[0,1,2],[0,2,10],[1,2,3],[2,3,1]]source = 0return = [0,2,5,6,-1]

Vertex 1 costs 2 to reach. Going through it reaches vertex 2 for 2 + 3 = 5, improving on the direct edge of cost 10. Vertex 3 then costs 6, and vertex 4 is unreachable.

Example 2

n = 3edges = [[0,1,0],[1,0,0],[1,2,7],[0,2,9]]source = 1return = [0,0,7]

From vertex 1, vertex 0 is reachable at cost 0. The direct edge to vertex 2 costs 7, which is better than cost 9 through vertex 0. The zero-cost cycle does not reduce any distance.

Constraints

1 <= n <= 3750.
0 <= edges.length <= 5000.
Each edge row has exactly 3 integers.
All edge fields are integers from 0 through 10^9.
Every edge endpoint is a vertex index from 0 through n - 1; the third field is its weight.
0 <= source < n.