ABC070 D - Transit Tree Path

問題
提出コード

解法

最短経路を求める問題で、頂点数があるので、各クエリごとにダイクストラ法を適用していたのでは間に合いそうにありません。
そこで、経由する点がで固定であり、この木が無向グラフであることに注目すると、から各頂点への最短距離を前計算で求めておけば、番目のクエリに対して、からまでの最短距離と、からまでの最短距離の和を求めるだけで、番目のクエリの答えになります。
ということで、までの入力を受け取った段階で、を始点とした各頂点に対する最短距離をダイクストラ法で求めるだけで、でクエリにこたえることができるので、これで間に合います。
今回のダイクストラ法は、とても基本的で、一番シンプルなものなので、ダイクストラ法の練習にもなると思います。