きままにものづくり

日々の気付いたことなんかを書いてます。

SRM584Div1Easy

問題

ある国にはN人の国民がおり、それぞれ貯金を持っている。この国のルールとして貯金額の差がdより大きい人同士では友達になることはできない。
友人関係を示す情報とdが与えられた時、国民間での貯金額の最大値を求めよ。有限値でない場合は-1を返す。

解法

最短路問題に帰着できる。
最短路の中での最大値にdをかけ合わせることで答えが求まる。
ワーシャルフロイドを用いているので計算量は O(N^3)だが他のアルゴリズムを用いることで、計算量の削減ができる。

計算量

 O(N^3)

コード

広告を非表示にする