Katkat
Back

Minimize shortest path by adding weight-1 edges

MathWorksSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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