優先度付き幅優先探索(最小コストの算出)

内容

よくある最短経路や最小コストを求める問題。
ダイクストラの拡張例みたいなもの。

生成された状態空間の中でもっともコストの小さい状態を抽出。
抽出された状態がゴールならそれが最小。
抽出された状態から次の状態を状態空間に挿入していく。

集合から最小を抽出するので、setとかpriority_queueが有効。
ただ、setの方がタイピングがしやす（ｒｙ

問題例

実装例

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
#define rep(n) REP(i,n)
int n,m,l;

typedef pair<int,int> S; // 残りのお金,現在地
typedef pair<int,S> pp;  // 襲われた人数を優先

const int INF = 10000000;
const int MXN = 102;
bool visited[MXN][MXN];
int cost[MXN][MXN];
int damage[MXN][MXN];

int main()
{
    while(cin>>n>>m>>l&&(n||m||l))
    {
        REP(i,MXN) REP(t,MXN){ cost[i][t]=INF; damage[i][t]=INF; visited[i][t]=false; }

        int a,b,d,e; rep(m)
        {
            cin>>a>>b>>d>>e; // 隣接行列で表現(*双方向移動可)
            cost[a][b] = d; damage[a][b] = e;
            cost[b][a] = d; damage[b][a] = e;
        }

        set<pp> s;                 // 状態の集合
        s.insert( pp(0,S(l,1)) );  // 初期状態 損害=0,残り=l,場所=1

        while(!s.empty())
        {
            pp p = *s.begin(); s.erase(s.begin()); // 最小を取り出す

            int vv = (p.second).second; // 場所
            int cc = (p.second).first;  // 残りの資金
            int dd = (p.first);         // 損害

            if( vv == n ){ cout<<dd<<endl; break; }
            if( visited[vv][cc] ) continue; else visited[vv][cc]=true;

            rep(n+1) // 次の状態を生成
            {
                if( cost[vv][i] == INF ) continue; // 道がない場合は除く
                if( cost[vv][i]<=cc ) s.insert( pp(dd,S(cc-cost[vv][i],i)) ); // 支払う場合
                s.insert( pp(dd+damage[vv][i],S(cc,i)) );                     // 支払わない場合
            }
        }
    }
    return 0;
}

次に遷移可能な状態をすべて生成。
今まで生成した状態と、今作った状態の全てからまた最小を探して繰り返し。