[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 144 (1002ﾚｽ)
上下前次1-新

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

182: 2023/12/24(日)17:06 AA×


[240|320|480|600|100%|GIF|べ|ﾚｽ栞|ﾚｽ消]
182: [sage] 2023/12/24(日) 17:06:26.61 ヒープのほうが簡単なのはそれはそう セグ木だと2つのinfを持つことになるからクソキモい実装になる 頂点数NのダイクストラをN頂点の点更新セグ木に乗せる 初期化は全ノードinf-1、スタート地点の頂点を距離0 頂点を取り出す時はセグ木の二分探索の気持ちで最小要素を探せばよくO(logN) 最短距離が確定したら別配列に答えを格納してから自身をinfで更新 辺の伝播はinf未満の頂点に対して行えばよく、現在値の取得はO(1)で更新するならO(logN) フィボナッチヒープに負けてたわ　カス！ http://medaka.5ch.net/test/read.cgi/prog/1703346239/182
ヒープのほうが簡単なのはそれはそう セグ木だとつのを持つことになるからクソキモい実装になる 頂点数のダイクストラを頂点の点更新セグ木に乗せる 初期化は全ノードスタート地点の頂点を距離 頂点を取り出す時はセグ木の二分探索の気持ちで最小要素を探せばよく 最短距離が確定したら別配列に答えを格納してから自身をで更新 辺の伝播は未満の頂点に対して行えばよく現在値の取得はで更新するなら フィボナッチヒープに負けてたわ カス！

---

上下前次1-新書関写板覧索設栞歴

---

あと 820 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 0.022s