[AtCoder] ABC070 D – Transit Tree Path

Transit Tree Path

典型的なグラフ問題です。

https://atcoder.jp/contests/abc070/tasks/abc070_d

考え方

題意

与えらたグラフにおける頂点 \( K \) を経由する二点間の最短距離を答えます。ただし、与えられる二点間は \( Q \) 個あります。

方針

普通の二点間の最短距離のクエリに答えるには、全点間の最短距離を得る必要があります。しかし、経由する頂点が与えられているので、頂点 \( K \) からその二点間の最短距離の和を答えれば良いです。したがって、単一点間の最短距離が分かれば良いので、ダイクストラ法を使います。

コード

感想

ダイクストラ法の復習になりました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする