「AOJ1156 Twirling Robot」の編集履歴(バックアップ)一覧に戻る
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156
コストが0, 若しくはc0, c1, c2, c3 で与えられるのでダイクストラする
BFSは一種のダイクストラで、普通各ノード間のコストが1のときをいう
またこの問題でノードは座標と方向を組み合わせたものにあたり、考えるべき要素が多くなっている
ここで座標, 方向, スタート地点からのコストの4つの要素を状態として持つ以下の様な構造体Stateを考える
struct State { int x, y, d, cost; State() {} State(int x, int y, int d, int cost) : x(x), y(y), d(d), cost(cost) {} ... };
これをpriority_queueに入れて解く。
(今回のようにノードの情報が座標と方向で要素が多いとき頂点が増えるので O(|V|^2) の ダイクストラを使うと失敗することが多い。よってO(|E|log|V|)のpriority_queueを使ったダイクストラを使うのが懸命)
但し構造体Stateを定義した場合、比較演算子が定義されてないのでoperatorを使って定義しなければならない
また、priority_queueで最小コストを持つStateを取り出すためはgreaterを指定する必要がある。よってoperatorは < でなく > を定義する必要がある
蛇足事項
以上より構造体Stateは以下のように記述できる
struct State { int x, y, d, cost; State() {} State(int x, int y, int d, int cost) : x(x), y(y), d(d), cost(cost) {} bool operator > (const State &s) const { return cost > s.cost; } };
priority_queueは通常コンテナの指定を省略できるが、priority_queueにgreaterなどのプレディゲートを指定するときはコンテナを指定しないといけない。priority_queueはデフォルトでvectorがコンテナになっているので
priority_queue<State, vector<State>, greater<State> > Q;
としておけば良い
ちなみにgreaterを指定しなくてもoperatorの内容をほんの少し弄れば同様のことが出来るようになる
ここでoperatorについて蛇足
operatorの書き方は、struct{...};の外に出して
struct {...}; bool operator>(const State &s1, const State &s2) const { return s1.cost>s2.cost; }
としてもよい。構造体やクラス内に埋め込む場合、const State &s1が自分自身を指すため省略できると考えてみると分かりやすいかも知れない
以下、擬似コード
(ダイクストラで辺のコストを減少させる操作を 緩和(relax) という)
Dijkstra PRIORITY QUEUE <State> Q 初期化処理 スタート地点のコスト = 0 ENQUEUE(Q, s) while Q is not empty u = DEQUEUE(Q) IF 既に求めたコストの方が小さい CONTINUE IF ゴール地点 RETURN u.cost FOR 現在地から四方向 v = u v.cost += グラフの情報と向きが同じかどうか判定してコストを追加 vの位置や向きを変える RELAX END FOR END WHILE RETURN INF