Livedoorブログからの移動
はてなブログからの移動

D - Transit Tree Path

解き方

  • aからKへの距離とKからbへの距離の和を出力する
  • Kから各頂点への最短距離は、木なので、DFSすればO(n)で求まる。

ハマったところ

  • 0-indexと1-index混ぜてた
    • 読み込み時に変えておくべきという話はありそう
  • 最初全頂点から全頂点を求めようとして、O(n^2)になって困ってた。

github.com