[伯俊/Python]1967樹の直径

https://www.acmicpc.net/problem/1967

アルゴリズム分類

BFS

問題を解く

基本アルゴリズムは次のとおりです.
ルートノード1から、すべてのパスで最大値を持つノード番号を求める.
そしてその番号から最大値を求めればいいです.
tree dicksherは次のように表される.
{1: [(2, 3), (3, 2)], 2: [(1, 3), (4, 5)], 3: [(1, 2), (5, 11), (6, 9)], 4: [(2, 5), (7, 1), (8, 7)], 5: [(3, 11), (9, 15), (10, 4)], 6: [(3, 9), (11, 6), (12, 10)], 7: [(4, 1)], 8: [(4, 7)], 9: [(5, 15)], 10: [(5, 4)], 11: [(6, 6)], 12: [(6, 10)]}
アクセスリストでアクセスすると、1に変わります.
次に、1番ノードからBFSに拡張し、各ノードは中間の重み値を増加し続け、重み値が最大の場合、その値とそのノード番号が格納される.
そしてそのノード番号からbfs関数を再び繰り返す.
今回はその値をプリントアウトして正解です.
(dicksherryに存在しない鍵を初めてクエリしたときに発生したKeyErrorに何が起こったのか、bfs(0)...なので0日からTree DickShownuryを作って解決しました…)

ソースコード

from collections import deque

n=int(input())
tree={i:[] for i in range(n+1)}
for i in range(n-1):
  a,b,weight=map(int, input().split())
  tree[a].append((b,weight))
  tree[b].append((a,weight))

def bfs(s):
  queue=deque()
  queue.append((s,0))
  visited=[0]*n
  visited[s-1]=1

  result=[0,0]
  while queue:
    now,cnt=queue.popleft()
    for i in tree[now]:
      next_number,value=i[0],i[1]
      if visited[next_number-1]==0:
        visited[next_number-1]=1
        queue.append((next_number,cnt+value))
        if result[1]<cnt+value:
          result[0]=next_number
          result[1]=cnt+value

  return result

a=bfs(1)
b=bfs(a[0])
print(b[1])