编写一个程序来查找用 Python 在网络中传递消息需要多长时间

假设我们有一个数字和一个边列表。这n个不同的节点标记为0到N。这些节点正在形成网络。每条边都是无向图的形式(a,b,t)，这表示如果我们尝试从a到b或b到a发送消息，则将花费t时间。节点收到消息后，立即将消息泛洪到相邻节点上。如果所有节点都已连接，我们必须找出每个节点接收从节点0开始的消息要花费多长时间。

因此，如果输入为n=3 edges=[[0，1，3]，[1，2，4]，[2，3，2]]，那么输出将是9，因为第4个节点（节点号3）从0->1->2->3接收消息，这需要3+4+2=9的时间。

范例(Python)

让我们看下面的实现以更好地理解-

import heapq
from collections import defaultdict
class Solution:
   def solve(self, n, edges):
      graph = self.build_graph(edges)  
      visited = set()
      heap = [(0, 0)]
      while heap:
         current_total_time, node = heapq.heappop(heap)
         visited.add(node)  
         if len(visited) == (n + 1):
            return current_total_time
         for nei, time in graph[node]:
            if nei not in visited:
               heapq.heappush(heap, (current_total_time + time, nei))
   def build_graph(self, edges):
      graph = defaultdict(set)
      for src, dest, t in edges:
         graph[src].add((dest, t))
         graph[dest].add((src, t))
      return graph
ob = Solution()
n = 3
edges = [[0, 1, 3],[1, 2, 4],[2, 3, 2]]
print(ob.solve(n, edges))

输入值

3, [[0, 1, 3],[1, 2, 4],[2, 3, 2]]

输入值

9