結果

問題 No.3113 The farthest point
コンテスト
ユーザー ako yas
提出日時 2025-04-19 21:05:16
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,783 bytes
コンパイル時間 338 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 278,036 KB
最終ジャッジ日時 2025-04-19 21:05:24
合計ジャッジ時間 7,731 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

try:
    sys.setrecursionlimit(2 * 10**5 + 10)
except Exception as e:
    print(f"再帰の深度の設定失敗。{e}", file=sys.stderr)

def dfs(start_node, graph):
    distances = {}
    max_dist = -float('inf')
    farthest_node = start_node

    stack = [(start_node, 0)]
    visited_for_dist_calc = {}

    while stack:
        u, dist_u = stack.pop()

        if u in visited_for_dist_calc and visited_for_dist_calc[u] >= dist_u:
             continue
        visited_for_dist_calc[u] = dist_u
        distances[u] = dist_u

        if dist_u > max_dist:
            max_dist = dist_u
            farthest_node = u

        if u not in graph:
             continue

        for v, weight in graph[u]:
             new_dist_v = dist_u + weight
             if v not in visited_for_dist_calc or new_dist_v > visited_for_dist_calc[v]:
                 stack.append((v, new_dist_v))


    final_farthest_node = start_node
    final_max_dist = -float('inf')
    for node, dist in distances.items():
        if dist > final_max_dist:
            final_max_dist = dist
            final_farthest_node = node

    return final_farthest_node, final_max_dist


def solve():
    n = int(sys.stdin.readline())

    if n == 1:
        print(0)
        return

    adj = {}
    nodes = set()

    for _ in range(n - 1):
        u, v, w = map(int, sys.stdin.readline().split())
        if u not in adj: adj[u] = []
        if v not in adj: adj[v] = []
        adj[u].append((v, w))
        adj[v].append((u, w))
        nodes.add(u)
        nodes.add(v)

    if not nodes:
         print(0)
         return

    start_node = 1

    farthest_node_u, _ = dfs(start_node, adj)

    _, diameter = dfs(farthest_node_u, adj)

    print(diameter)

if __name__ == "__main__":
    solve()
0