Signal Spread Time
Problem
A network has n relays numbered from 0 and a list of one-way links (u, v, t): a signal at relay u reaches relay v after t minutes, where t is 0 or more. A signal leaves relay source at minute 0 and every relay forwards it along all of its links the moment it arrives. Return the minute at which the last relay receives the signal, or -1 if some relay never receives it.
Examples
Input: n = 4, source = 0
links = [(0, 1, 2), (0, 2, 5), (1, 2, 1), (2, 3, 3)]
Output: 6
Why: relay 2 hears it at minute 3 through relay 1, so relay 3 hears it at 6Input: n = 3, links = [(0, 1, 4)], source = 0
Output: -1
Why: nothing ever links to relay 2Input: n = 1, links = [], source = 0
Output: 0
Why: edge case, the source already has the signalHints
0 / 3
Each relay hears the signal at the time of its quickest route from the source. The question is really about shortest paths, and then about the slowest of them.
Link times are never negative, so the relay with the smallest known arrival time that is not yet settled can never be improved later.
Keep a min-heap of (arrival time, relay) starting with (0, source). Pop the earliest entry, skip it if that relay is already settled, otherwise settle it and push each neighbour with the arrival time plus the link time. At the end, check that all n relays were settled and return the largest time.
Solution
The arrival time at each relay is its shortest-path distance from the source, and with non-negative link times Dijkstra's algorithm finds all of them. A min-heap always hands back the earliest unsettled arrival, which is final because any other route would pass through a later relay first. Stale heap entries for relays already settled are skipped. If fewer than n relays get settled the answer is -1, otherwise it is the latest arrival. Time is O((n + m) log m) for m links, and space is O(n + m).
import heapq
def spread_time(n, links, source):
graph = [[] for _ in range(n)]
for u, v, t in links: graph[u].append((v, t))
arrival = {} # relay -> final arrival minute
heap = [(0, source)]
while heap:
time, relay = heapq.heappop(heap)
if relay in arrival: continue # a quicker route already settled it
arrival[relay] = time
for nxt, t in graph[relay]:
if nxt not in arrival: heapq.heappush(heap, (time + t, nxt))
return max(arrival.values()) if len(arrival) == n else -1
print(spread_time(4, [(0, 1, 2), (0, 2, 5), (1, 2, 1), (2, 3, 3)], 0)) # -> 6
print(spread_time(3, [(0, 1, 4)], 0)) # -> -1
print(spread_time(1, [], 0)) # -> 0Stuck on the idea rather than the code? Dijkstra's Algorithm covers it.