SRM584Div1Easy
問題
ある国にはN人の国民がおり、それぞれ貯金を持っている。この国のルールとして貯金額の差がdより大きい人同士では友達になることはできない。
友人関係を示す情報とdが与えられた時、国民間での貯金額の最大値を求めよ。有限値でない場合は-1を返す。
解法
最短路問題に帰着できる。
最短路の中での最大値にdをかけ合わせることで答えが求まる。
ワーシャルフロイドを用いているので計算量はだが他のアルゴリズムを用いることで、計算量の削減ができる。
計算量
ある国にはN人の国民がおり、それぞれ貯金を持っている。この国のルールとして貯金額の差がdより大きい人同士では友達になることはできない。
友人関係を示す情報とdが与えられた時、国民間での貯金額の最大値を求めよ。有限値でない場合は-1を返す。
最短路問題に帰着できる。
最短路の中での最大値にdをかけ合わせることで答えが求まる。
ワーシャルフロイドを用いているので計算量はだが他のアルゴリズムを用いることで、計算量の削減ができる。