숫자와 모서리 목록이 있다고 가정합니다. 이 n개의 서로 다른 노드는 0에서 N으로 레이블이 지정됩니다. 이 노드는 네트워크를 형성하고 있습니다. 각 간선은 무방향 그래프의 형태(a, b, t)이며, 이는 우리가 b 또는 b에서 a로 메시지를 보내려고 하면 t 시간이 걸린다는 것을 나타냅니다. 노드가 메시지를 받으면 즉시 이웃 노드로 메시지를 플러딩합니다. 모든 노드가 연결되어 있으면 모든 노드가 노드 0에서 시작하는 메시지를 수신하는 데 걸리는 시간을 찾아야 합니다.
따라서 입력이 n =3 edge =[[0, 1, 3],[1, 2, 4],[2, 3, 2]]와 같으면 출력은 4번째 노드( 노드 번호 3) 0 -> 1 -> 2 -> 3에서 메시지를 수신하는 데 3 + 4 + 2 =9 시간이 걸립니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
build_graph() 함수를 정의합니다. 가장자리가 필요합니다.
- 그래프 :=빈 지도
- 에지에 설정된 각 (src, dest, t)에 대해 수행
- 그래프[src]에 (dest, t) 삽입
- 그래프[dest]에 (src, t) 삽입
- 반환 그래프
- 메인 방법에서 다음을 수행하십시오 -
- 그래프 :=build_graph(에지)
- 방문함:=새로운 세트
- heap :=(0, 0) 쌍으로 새로운 힙 만들기
- 힙이 비어 있지 않은 동안 수행
- (current_total_time, node) :=힙의 최상위 요소, 힙에서 삭제
- 노드를 방문한 것으로 표시
- 방문한 노드의 수가 (n + 1)과 같으면
- current_total_time 반환
- 그래프[노드]의 각 쌍(nei, 시간)에 대해 수행
- 방문하지 않으면
- 힙에 쌍(current_total_time + time, nei) 삽입
- 방문하지 않으면
예제(파이썬)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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