Solutions

# Djikstra's shortest path, Bellman-Ford, DFS with pruning. Djikstra is optimal for sparse graphs, Bellman-Ford is optimal for dense graphs, and DFS is suboptimal but easy to implement.
# graphs


# Djikstra shortest path (BFS with min heap) - O(E log V) time, O(V + E) space
def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:
    from collections import defaultdict
    neighbors = defaultdict(list)
    for ui, vi, ti in times:
        neighbors[ui].append((vi, ti))

    
    import heapq
    heap = [(0, k)] # NB: time first, to allow ordering by min time
    visited = set()
    time = 0

    while heap:
        t, u = heapq.heappop(heap)
        if u in visited:
            continue

        visited.add(u)
        time = t

        for vi, ti in neighbors[u]:
            if vi in visited:
                continue

            heapq.heappush(heap, (ti + t, vi))

    return time if len(visited) == n else -1


# Bellman-Ford - O(V*E) time, O(V) space
def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:
    dist = [float("inf") for _ in range(n)]
    dist[k-1] = 0 # source

    # After n rounds of relaxation, all shortest paths are guaranteed to be found
    # because the longest path has at most n-1 edges
    for _ in range(n):
        for u, v, t in times:
            if dist[u-1] + t < dist[v-1]:
                dist[v-1] = dist[u-1] + t

    res = int(max(dist))
    return -1 if res == float("inf") else res


# DFS - O(2^V) time (subptimal pruning), O(V+E) space
def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:
    from collections import defaultdict
    neighbors = defaultdict(list)
    for ui, vi, ti in times:
        neighbors[ui].append((vi, ti))

    tmap = { i: 99999 for i in range(1, n+1) } # NB: nodes are 1-n

    def dfs(node: int, time: int):
        if time >= tmap[node]:
            return

        tmap[node] = time
        for vi, ti in neighbors[node]:
            dfs(vi, ti + time)
    
    dfs(k, 0)
    res = max(tmap.values())
    return -1 if res == 99999 else res