Minimize shortest path by adding weight-1 edges
Company: MathWorks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
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`
Quick Answer: This question evaluates proficiency in graph algorithms, shortest-path computation, and algorithmic optimization when augmenting a directed weighted graph with additional unit-weight edges.
Because any directed edge can be added with weight 1, return the minimum possible distance from node 1 to node n.
Constraints
- Added edges may have any endpoints and weight 1
Examples
Input: (5, [1, 2], [2, 5], [10, 10])
Expected Output: 1
Explanation: Add direct edge 1->n.
Input: (1, [], [], [])
Expected Output: 0
Explanation: Source equals target.
Input: (2, [], [], [])
Expected Output: 1
Explanation: Direct added edge.
Hints
- For n>1, a direct added edge from 1 to n gives distance 1, and positive weights cannot do better.