http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156
コストが0, 若しくはc0, c1, c2, c3 で与えられるのでダイクストラする
BFSは一種のダイクストラで、普通各ノード間のコストが1のときをいう
ここで座標x, y, 方向, スタート地点からのコストの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;
としておけば良い
ちなみにpriority_queueにgreaterを指定しないで（つまり自動でlessとなる）operatorの内容を弄って
bool operator < ( const &State s ) {
return cost > s.cost;
}
とすれば同様にpriority_queueから最小のコストを持つ状態を取り出せるようになる
operatorについて蛇足
operatorの書き方は、struct{...};の外に出して
struct {...};
bool operator>(const State &s1, const State &s2) const {
return s1.cost>s2.cost;
}
としてもよい。構造体やクラス内に埋め込む場合、const State &s1が自分自身を指すため省略できると考えてみると分かりやすいかも知れない
以下、擬似コード
Dijkstra
PRIORITY QUEUE <State> Q
初期化処理
スタート地点のコスト = 0
ENQUEUE(Q, s)
while Q が空でない
u = DEQUEUE(Q)
IF 既に求めたコストの方が小さい CONTINUE
IF ゴール地点 RETURN u.cost
FOR 現在地から四方向
v = u
v.cost += 与えられたグラフの情報と向きが同じかどうか判定してコストを追加
vの位置や向きを更新
IF コスト更新出来るか
ENQUEUE(Q, t)
コスト更新
END IF
END FOR
END WHILE
RETURN INF