알고리즘/백준
[백준] 1167번 트리의 지름 (파이썬)
알감자
2022. 1. 5. 23:21
1167번: 트리의 지름
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지
www.acmicpc.net
코드
import heapq
import sys
v = int(input())
li = [[] for _ in range(v+1)]
for _ in range(v):
input_li = list(map(int, input().split(" ")))
for i in range(1, len(input_li)-1,2):
node = input_li[i]
length = input_li[i+1]
li[input_li[0]].append([node, length])
INF = sys.maxsize
def dikstra(start):
destination = [INF] * (v+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
d1 = dikstra(1)
print(max(dikstra(d1.index(max(d1[1:])))[1:]))