ABC070 D: Transit Tree Path
解き方
aからKへの距離とKからbへの距離の和を出力するKから各頂点への最短距離は、木なので、DFSすればO(n)で求まる。
ハマったところ
- 0-indexと1-index混ぜてた
- 読み込み時に変えておくべきという話はありそう
- 最初全頂点から全頂点を求めようとして、
O(n^2)になって困ってた。
aからKへの距離とKからbへの距離の和を出力するKから各頂点への最短距離は、木なので、DFSすればO(n)で求まる。O(n^2)になって困ってた。