「AOJ1156 Twirling Robot」の編集履歴（バックアップ）一覧に戻る
*AOJ1156 Twirling Robot
**サイト
[http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156]
**解説
コストが0, 若しくはc0, c1, c2, c3 で与えられるのでダイクストラする
BFSは一種のダイクストラで、普通各ノード間のコストが1のときをいう
ここで座標, 方向, コストの状態を持つ以下の様な構造体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を使うためにoperatorを定義しなければならない
このときpriority_queueで最小コストを持つStateを取り出すためgreaterを指定する必要があるので、operatorは < でなく > を定義する必要があることに注意
（通常のsort関数などはgreaterを指定すると降順に並ぶが、priority_queueはgreaterを指定すると最小を取り出すようになる）
よって構造体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
||<
