白駿-グラフ(#1967)
8880 ワード
https://www.acmicpc.net/problem/1967
#1167類似の問題
https://velog.io/@starteon/%EB%B0%B1%EC%A4%80-%EA%B7%B8%EB%9E%98%ED%94%84-1167
Code
import sys
sys.setrecursionlimit(10**9)
def dfs(node):
for e,d in tree[node]:
if dist[e] == 0:
dist[e] = dist[node] + d
dfs(e)
# make tree
n = int(input())
tree = {x:[] for x in range(1,n+1)}
for _ in range(n-1):
inp = list(map(int, sys.stdin.readline().split()))
tree[inp[0]].append([inp[1],inp[2]])
tree[inp[1]].append([inp[0],inp[2]])
# find the farthest node from node 1
dist = [0]*(n+1)
if n > 1:
dfs(1)
dist[1] = 0
farthest_node = 0
cnt = 0
for i in range(1,n+1):
if dist[i] > cnt:
cnt = dist[i]
farthest_node = i
# find the farthest node from node 1
dist = [0]*(n+1)
if n > 1:
dfs(farthest_node)
dist[farthest_node] = 0
result = 0
for i in range(1,n+1):
if dist[i] > result:
result = dist[i]
farthest_node = i
print(result)
リファレンス
#1167類似の問題
https://velog.io/@starteon/%EB%B0%B1%EC%A4%80-%EA%B7%B8%EB%9E%98%ED%94%84-1167
Reference
この問題について(白駿-グラフ(#1967)), 我々は、より多くの情報をここで見つけました https://velog.io/@starteon/백준-그래프-1967テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol