2012-04-28から1日間の記事一覧
問題概要 兵士がN( 解法 実はこのままではこの問題は解けず、「合流はない」という条件を付け加えなければならない。 最短経路に使われる辺だけを(有向化して)残すと辺の重みが正なのでDAGになる(距離の近い順がそのままトポロジカル順序になっている)。求め…
問題概要 兵士がN( 解法 実はこのままではこの問題は解けず、「合流はない」という条件を付け加えなければならない。 最短経路に使われる辺だけを(有向化して)残すと辺の重みが正なのでDAGになる(距離の近い順がそのままトポロジカル順序になっている)。求め…