Problem statement

https://binarysearch.com/problems/Distributed-Systems/

Solution

Just use classical Dijkstra here.

Complexity

It is O((E + V) log V) for time and O(E + V) for space.

Code

class Solution:
    def solve(self, n, edges):
        dist = [float('inf')] * (n + 1)
        dist[0] = 0
        G = defaultdict(list)
        
        for a, b, w in edges:
            G[a].append((b, w))
            G[b].append((a, w))
        
        heap = [(0, 0)]

        while heap:
            min_dist, idx = heappop(heap)
            for neibh, weight in G[idx]:
                cand = min_dist + weight
                if cand < dist[neibh]:
                    dist[neibh] = cand
                    heappush(heap, (cand, neibh))
                    
        return max(dist)