CODE FESTIVAL 2014 上海オープンコンテスト D : Maze
クソ雑魚なので参加してません。
オンライン参加です。
問題↓
D: Maze - code festival 2014 上海(オープンコンテスト) | AtCoder
問題概要
- 迷路があります。
- ゴール2種類あります。(A,B)
- スタートからゴールへ行く道のりは必ず最短でなければいけません。
- 各ゴールへ行く時の道筋が被ってはいけません。
- スタートから各ゴールへの経路を出力して下さい。
(output は 問題を見た方が分かりやすいです。)
解法
- 最初に、bfsでスタートからゴールへの最短経路を求めます。
- 次にスタートから流量2の最小費用流を流します。
- 最小費用流 が 各ゴールへの最短経路の和 と等しければ 4 へ、異なれば "NA"
- 最小費用流の経路復元をしてdfsでゴールまでの経路を書き換えます。
- 最小費用流のグラフを作るときに、各マスについて受け取るノードと配るノードに分けないと上手くいかないので注意。
(同じノードを通ってはいけないので ( 受け取るノード -> 配るノード , cap=1, cost = 0 ) を張らなければならない) - フローの経路復元は cap の値が減っているかどうかを見ればよい。
今回はcap が 1 なので(受け取るノード -> 配るノード の cap = 0) になっているようなマスを仮に'x'と置く。 - dfs は 本当に愚直に行えばOK。x を 辿って 各ゴールに最短でたどり着けば良い。
ソースコード
感想
最初に送ったコードがよく分からないバグでTLEしててDFSにいらん工夫を加えまくった結果バグに悩まされた。
結局愚直にガリガリDFS書いたらに通ってしまった。オーダー的に間に合うのよく分からんなぁ(分岐多そう)