Shortest Reach in a Graph in Hacker Rank

問題

n個のノードとm個のエッジによって構成されるグラフが与えられ、スタートノードからその他の全てノードまでの最短距離を求める問題。

www.hackerrank.com

解法

優先度付きキューを用いたダイクストラ法を使って解く

計算量

優先度付きキューに値を追加する操作と取り出す操作はO(logN)で行えるの。 グラフにおけるノードの数をV、エッジの数をEとすると優先度付きキューを用いたダイクストラ法の計算量はO((V + E)logV)となる。今回、2 ≦ V ≦ 10^3, 1 ≦ E ≦ V(V-2)/2なので**O(106log103)となる。また、この処理をクエリーの数q(1 ≦ q ≦ 10)だけ行うので最終的な計算量はO(107log103)となる。

クラスのプロパティによってオブジェクトをソートする

今回優先度付きキューに入れるのは自作したクラスのオブジェクトだ。オブジェクトの持つdistanceプロパティの値によってソートさせたい。こういう時は自作したクラスに対してimplements ComparableとしてcompareToメソッドを実装することで実現できる。

ソースコード