Compute Minimum Broadcast Latencies Between Cities

Problem Statement

A streaming service is deploying an updated live-broadcasting mesh network across n cities, labeled 0 to n - 1. You are given an integer n, a list of bidirectional connections links, and a starting city src.

Each element in links is a triplet [u, v, latency], representing an undirected network link between city u and city v with a transmission latency of latency milliseconds.

There may be multiple parallel links between the same pair of cities, as well as self-loops. Compute the minimum time required for a broadcast originating at src to reach each city from 0 to n - 1. If a city cannot be reached from src, its latency should be -1.

Function Signature

def min_broadcast_latencies(n: int, links: list[list[int]], src: int) -> list[int]:
    pass

Input & Output Format

• Input:
  • n: Total number of cities (1 <= n <= 10^4).
  • links: List of connections where each link is [u, v, latency] (0 <= len(links) <= 5 * 10^4, 0 <= u, v < n, 0 <= latency <= 10^9).
  • src: The origin city (0 <= src < n).
• Output:
  • A list of n integers where the i-th value is the minimum latency from src to city i. The latency to src is always 0.

Examples

Example 1

Input: 
n = 4
links = [[0, 1, 10], [0, 2, 30], [1, 2, 10], [1, 1, 5]]
src = 0

Output: [0, 10, 20, -1]

Explanation:
- City 0 is the source, distance = 0.
- City 1 is reached directly with latency 10.
- City 2 can be reached via City 1 (10 + 10 = 20), which is faster than the direct link (30).
- City 3 has no links connecting to it, so its latency is -1.

Example 2

Input:
n = 3
links = [[0, 1, 50], [0, 1, 20], [1, 2, 15]]
src = 0

Output: [0, 20, 35]

Explanation:
Among parallel links between 0 and 1, the link with latency 20 is optimal. City 2 is reached via City 1 with total latency 20 + 15 = 35.

Edge Cases

• Disconnected components should have a result of -1.
• Parallel edges between identical nodes with different weights.
• Self-loops (u == v) should not create cycles or overwrite the source distance of 0.