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.