拡張ダイクストラ法についてのメモ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0212

解法: 拡張ダイクストラ 個人的なイメージでは3次元空間で上から下に下ろしてく感じ

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<string>
#include<sstream>
#include<queue>
#include<climits>
#include<numeric>
#include<functional>
#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define fi(i,j,k) fill(i[0],i[0]+j*j,k)
#define INF 1<<25
#define smax 105
static const double eps=1e-10;
typedef long long ll;
typedef std::pair<int,int> P;
using namespace std;
typedef pair<int,P> pp;

vector<P> edge[smax];
int c,n,m,s,d; // c...割引券枚数 n...頂点 m...辺 s...出発点 d...終点 
int v[15][smax]; //15....max of tickets

int solve(){
   v[c][s] = 0; //初期化
   priority_queue<pp,vector<pp>,greater<pp> > q;
   q.push(pp(0,P(s,c))); //cost,now,ticket(now)
   while(!q.empty()){
      pp V = q.top();
      q.pop();
      int now_v = V.second.first;
      int now_t = V.second.second;
      if(v[now_t][now_v] < V.first) continue; //v.first(コスト)がv[now_t][now_v]がより大きかったら調べる必要性はない

      //not use tickets
      for(int i=0;i<edge[now_v].size();i++){
         if(v[now_t][edge[now_v][i].first] > v[now_t][now_v]+edge[now_v][i].second ){
            v[now_t][edge[now_v][i].first] = v[now_t][now_v]+edge[now_v][i].second;
            q.push(pp(v[now_t][now_v]+edge[now_v][i].second,P(edge[now_v][i].first,now_t)));
         }
      }

      // use tickets
      if(now_v > 0){
         for(int i=0;i<edge[now_v].size();i++){
            P p = edge[now_v][i];
            int next_c = p.second /2;
            if(v[now_t-1][p.first] > v[now_t][now_v] + next_c){
               v[now_t-1][p.first] = v[now_t][now_v] + next_c;
               q.push(pp(v[now_t-1][p.first],P(p.first,now_t-1)));
            }
         }
      }
   }
   int ans = INF;
   for(int i=0;i<c+1;i++){
      ans = min(ans,v[i][d]);
   }
   return ans;
}

int main(void){
   while(cin >> c >> n >> m >> s >> d && c|n|m|s|d){
      rep(i,smax) edge[i].clear();
      fill(v[0],v[0]+15*smax,INF);
      rep(i,m){
         int a,b,f;
         cin >> a >> b >> f;
         edge[a].push_back(P(b,f));
         edge[b].push_back(P(a,f));
      }
      cout << solve() << endl;
   }
   return 0;
}