結果

問題 No.3113 The farthest point
ユーザー tufusa
提出日時 2025-04-19 18:30:27
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 641 bytes
コンパイル時間 421 ms
コンパイル使用メモリ 8,192 KB
実行使用メモリ 146,372 KB
最終ジャッジ日時 2025-04-19 18:30:35
合計ジャッジ時間 7,489 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

n = gets.to_i
g = Array.new(n) { [] }
(n - 1).times do
  u, v, w = gets.split.map(&:to_i)
  next if w < 0

  u -= 1
  v -= 1
  g[u] << [v, w]
  g[v] << [u, w]
end

def dfs(g, seen, now, cost)
  max = [now, cost]
  g[now].each do |nxt, w|
    next if seen[nxt]

    seen[nxt] = true
    res = dfs(g, seen, nxt, cost + w)
    max = res if max[1] < res[1]
  end

  max
end

max = 0
seen = Array.new n, false
n.times do |i|
  next if seen[i]

  seen.fill(false).tap { _1[i] = true }
  far1 = dfs(g, seen, i, 0)[0]

  seen2 = Array.new(n, false).tap { _1[far1] = true }
  far2 = dfs(g, seen2, far1, 0)[1]
  max = far2 if max < far2
end

puts max
0