알고리즘/백준
[백준] 1967번 트리의 지름 (파이썬)
알감자
2022. 1. 5. 23:23
1967번: 트리의 지름
파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연
www.acmicpc.net
코드
import heapq
import sys
n = int(input())
li = [[] for _ in range(n+1)]
for _ in range(n-1):
a, b, weight = map(int, input().split(" "))
li[a].append([b,weight])
li[b].append([a,weight])
INF = sys.maxsize
def dikstra(start):
destination = [INF] * (n+1)
destination[start] = 0
heap = []
heapq.heappush(heap, [destination[start], start])
while heap:
weight, node = heapq.heappop(heap)
for next_node, next_weight in li[node]:
new_weight = weight + next_weight
if new_weight < destination[next_node]:
destination[next_node] = new_weight
heapq.heappush(heap, [new_weight, next_node])
return destination
destination = dikstra(1)
print(max(dikstra(destination.index(max(destination[1:])))[1:]))