Coding questions · MathWorks

Minimize shortest path by adding weight-1 edges

This question evaluates proficiency in graph algorithms, shortest-path computation, and algorithmic optimization when augmenting a directed weighted graph with additional unit-weight edges.

You are given a weighted directed graph with nodes labeled 1..n.

The existing edges are described by three arrays of equal length m:

from[i]: start node of edge i
to[i]: end node of edge i
weight[i]: positive weight of edge i

You are allowed to add any number of additional directed edges, where each added edge has weight = 1, and you may choose its endpoints (any nodes in 1..n).

After adding edges optimally, compute the minimum possible shortest-path distance from node 1 to node n.

Input

n: number of nodes
from[0..m-1], to[0..m-1], weight[0..m-1]

Output

An integer: the smallest achievable distance from 1 to n after adding weight-1 edges.

Notes / Constraints (reasonable for interviews)

1 <= n <= 2e5
1 <= m <= 2e5
1 <= weight[i] <= 1e9

Minimum Shortest Path After Adding Weight-1 Edges

Because any directed edge can be added with weight 1, return the minimum possible distance from node 1 to node n.

Examples

Example 1

Input: (5, [1, 2], [2, 5], [10, 10])
Output: 1

Explanation: Add direct edge 1->n.

Example 2

Input: (1, [], [], [])
Output: 0

Explanation: Source equals target.

Hints

For n>1, a direct added edge from 1 to n gives distance 1, and positive weights cannot do better.