ABC012D
考えたこと
最も遠い頂点までの距離が最小になる点を選んだ時の、その距離を求める問題だと
グラフの半径だね
全方位木DPで求めるんだったかな
そんな難しいことをこの難易度で聞かれるかな
あっ、これ木じゃないぞ？
ワーシャルフロイド法でO(V^3)か
Vは300なので間に合う？
公式解説
ダイクストラ法O(V^2)をV回やるかワーシャルフロイド
「ただしPythonなどの遅い言語では通らないことが検証済み」(ええー)
ダイクストラをO((E+V)log V)でやる案
これ試してみよう
PythonでもあっさりACしました
5秒制限のところ1.4秒
6年前の問題だからジャッジマシンが早くなったのかな？
それとも「通らないことが検証済み」ってのはV^3の解法のことかな
pythondef solve(N, M, edges):
INF = 9223372036854775807
ret = INF
for start in range(N):
distances = [INF] * N
distances[start] = 0
queue = [(0, start)]
while queue:
d, frm = heappop(queue)
if distances[frm] < d:
# already know shorter path
continue
for to in edges[frm]:
new_cost = distances[frm] + edges[frm][to]
if distances[to] > new_cost:
# found shorter path
distances[to] = new_cost
heappush(queue, (distances[to], to))
ret = min(ret, max(distances))
return retRelated Pages
- →chokudai×貪欲法の証明パターン×選択肢が少ない方から貪欲×マトロイド×クラスカル法×区間スケジューリング×交換しても悪化しない×アルゴリズムとデータ構造×区間はマトロイドではない×abc076b×現在が良いほど未来も良い×poj3617×poj3069×ダイクストラ法×agc009a×arc111×abc187×arc110c×一回り小さい同じ形の問題×agc049b×abc103d×abc023d×和の比率の最大化×単位時間ジョブスケジューリング問題×乱択＋貪欲×abc171_f×離散凸性→
- →past5×past202012×アルゴリズム実技検定×past過去問練習202012×past5e×past5f×past5g×past5h×PAST5I×past5j×past5k×past5l×past5m×past5n×past5o×番兵×地図読み込み時に番兵をつける×ゴールをスタートにする×ゴールを一つにする×ダイクストラ法×bit_dp×期待値dp×二次元の片方を時間軸にする×past2n→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]