Minimize shortest path by adding weight-1 edges

Q: 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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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

Minimize shortest path by adding weight-1 edges

Quick Overview

Comments (0)