SRM 612
「朝トップコーダーに参加 → 朝から他人のコードのバグを探すのに集中 → 日中の仕事で、コードレビュー時に他人のバグを発見しやすくなる。→ 出世・昇給 → もてまくり！」 by @nico_shindannin
-
masashinakata
- 7117
- 0
- 0
- 0
-
- いいね！0
はむこ
@hamko_intel
@not_522 01の場合は、0を先に取っていけばいいのはわかります。しかし、辺の重みが12の場合は、1を延々と取っていけば良いとは限らないので、辺が離散的にソートされていたとしても、未確定頂点のソートが必要になる気がして困っています…。
2017-02-16 02:34:40
はむこ
@hamko_intel
@not_522 頂点がV = {0, 1, 2, 3}に対して、edge = (from, to, cost)がedges = {(0, 1, 1), (1, 2, 1), (2, 3, 1), (0, 3, 2)}で、どう動けば0->3の最小距離を求まるのでしょうか。。
2017-02-16 02:36:46
はむこ
@hamko_intel
「重みが整数でかつ最短路の距離がある定数Wで抑えられる場合、ダイクストラ法を適切に実装することでO(E+W)時間で解ける。 重みが整数の場合、理論的には一般の場合よりも速い計算量で解くことができる。」How...yukicoder.me/wiki/shortest_…
2017-02-16 02:40:10
koyumeishi
@koyumeishi_
@ryo_wk ideone.com/kzhBOt こういう事だと思います（適当に書いたのでどっかバグってるかも）。 01-bfs のように差分だけを持つパターンも ideone.com/P5JGPt
2017-02-16 03:11:44
はむこ
@hamko_intel
やさしいせかい #はてなブログ ダイクストラと整数辺BFSなどめっちゃ色々試した TopCoder SRM 612 Div1 Easy EmoticonsDiv1 - はむこの勉強記録 hamko.hatenadiary.jp/entry/2017/02/…
2017-02-16 09:26:18