Minimum Latency Network Routing via Dijkstra

An electronic trading firm routes market orders through a private fiber-optical colocation network connecting $N$ data centers labeled $0$ to $N - 1$. Direct optical links are represented as directed edges (u, v, latency) with physical propagation delay latency.

In addition, each data center node $v$ introduces a hardware switch processing overhead hop_delays[v]. Therefore, the total latency incurred in traversing link $u \to v$ is: $\text{cost}(u \to v) = latency + hop\_delays[v]$

Your Task

Implement min_latency_network_routing(n: int, edges: list[tuple[int, int, int]], hop_delays: list[int], source: int) -> tuple[dict[int, int], int] that computes:

1. A dictionary mapping each reachable node $v$ to the minimum total latency from source to $v$ (node source initial latency is $0$).
2. The maximum latency among all reachable nodes in the network.

Constraints

• $1 \le n \le 5000$
• $0 \le \text{len}(edges) \le 50000$
• $latency \ge 0$, $hop\_delays[v] \ge 0$
• $0 \le source < n$

Examples

n = 3
edges = [(0, 1, 10), (1, 2, 20), (0, 2, 50)]
hop_delays = [0, 5, 5]
source = 0
# 0 -> 1: latency 10 + hop 5 = 15
# 0 -> 1 -> 2: 15 + latency 20 + hop 5 = 40
# 0 -> 2 direct: latency 50 + hop 5 = 55
# Min distances: {0: 0, 1: 15, 2: 40}, Max latency = 40