AOJ 1162 - Discrete Speed - つらねの日記

問題

指定された都市から都市へ移動するためにかかる時間を求める。自機は速度を持っており、スタートの都市からは速度1で出発しゴールの都市へは速度1で到着する。各都市では減速または加速を行うことができる。道路には制限速度があり、それを超えた速度を出すことはできない。Uターンは禁止。

注意した点

ダイクストラを使って解く。
参考：ダイクストラ法 - Wikipedia

各街毎に在る道を配列として保有する。

        vector<vector<edge>> E(city_n + 1);

前は配列を使ったが、vector>の方が良いらしい。
無向グラフなので双方向に接続する。
要素数を city_n + 1 確保しているのは街番号が 1 -> city_n のため、1引いたり足したりする場所を考える手間を省くため。

その都市、前の都市(pcity)、速度ごとにそれぞれ最短の時間であった時を保管する配列を作る。

        vvvf G(city_n + 1, vvf(city_n + 1, vf(MAX_SPEED + 1, INF)));

同一の条件で今より少ない時間で到達していたならその探索を取りやめるために必要。

G に pcity 分の次元が必要な理由について

上の図について、丸が都市・線が道路とする。青数字は道路の長さを示す。
1から4に行く経路は124と134の二つのケースがある。134を通った場合、Uターンが禁止なので次に都市3に行くことができない。したがって前の都市の次元も含めてテーブルGを作る必要がある。

時間毎に自動でソートするキュー。

priority_queue<P, vector<P>, greater<P>> que;
||<<
これに初速0のPを追加しておくことによってスタートの都市で加速して速度1でスタートの都市を出発することができる。

都市についたら都市に隣接するすべての道路を見る。
>|cpp|
   for(auto e : E[p.city]) {
        if(e.to == p.pcity) continue;
           FOR(d, -1, 1 + 1){
||<<
Uターンでなく制限速度を守ったうえで、そのうえで以前より短い時間で行くことができるのならキューに挿入する。
この際に、減速・等速・加速の三種類を挿入しておく。