Compute minimax grid path and network delay

Problem (two related shortest-path tasks)

Part 1 — Minimize the maximum value along a grid path ("minimax" path)

You are given an m x n integer grid H, where H[r][c] is the “difficulty/height” of cell (r,c).

• Start at (0,0) and want to reach (m-1, n-1) .
• You may move up/down/left/right to adjacent cells (no diagonals).
• The cost of a path is not the sum of values; instead it is:

the maximum H[r][c] value encountered on that path (including start and end).

Return the minimum possible path cost (i.e., minimize the maximum cell value you ever step on).

Assumptions/constraints (typical interview constraints):

• 1 <= m,n <= 200
• 0 <= H[r][c] <= 10^9

Part 2 (follow-up) — Time for a signal to reach all nodes in a weighted graph

You are given a weighted graph with n nodes labeled 1..n and a list of directed edges edges, where each edge is (u, v, w) meaning it takes time w > 0 to travel from u to v.

A signal starts at node k at time 0 and travels along edges.

• Let dist[i] be the shortest time for the signal to reach node i .
• Return :
  • max(dist[i]) over all nodes i if every node is reachable, or
  • -1 if some node is unreachable.

Assumptions/constraints (typical interview constraints):

• 1 <= n <= 10^5 (or smaller in an interview)
• 1 <= |edges| <= 2*10^5
• 1 <= w <= 10^9

Edge cases to consider

• Start equals end (Part 1: m=n=1 ; Part 2: n=1 ).
• Unreachable nodes (Part 2).
• Multiple edges between the same nodes (Part 2).
• Repeated states pushed into a heap/priority queue (both parts).