ZONeエナジー プログラミングコンテスト “HELLO SPACE” E - 潜入 (500)
愚直にダイクストラ法で解こうとすると頂点数が$ \mathcal{O}(N)、辺が$ \mathcal{O}(N^3)になってTLEする
以下の最良優先探索を枝刈りしながら行うとC++では間に合う
4種類の内、上3種類は訪問先のコストが今計算した結果より大きいなら移動してキューに入れる
一番下の移動は現在の点に近い方から見ていく
その点が既に訪問済みの場合はそこでストップする
先に見ていると言うことはその点のコストは現在の点と同等以下
その点からの移動の方が追加コストも低いので現在の点から移動する必要は無い
コストが小さくなる場合にだけ移動する枝刈りが効果的だった
解説の方法
頂点を普通の状態と4番目の移動中の2種類に増やす
自身の移動中へのコストは1
移動中から普通状態への移動コストは0
移動中から移動可能なところへの移動コストは1
ダイクストラ法で解こうとすると頂点数が$ \mathcal{O}(N)、辺が$ \mathcal{O}(N^2)になって間に合う