AOJ Highway Express Bus

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

最短経路を求める問題ですが、道中に枚割引券を使うことができます。
として、拡張Dijkstraをやります。 は今持っている割引券の枚数です。
nowに対して、割引券を使う方と使わない方をqueにpushします。
なんだか拡張Dijkstraはプログラミングしてる感があるので好きです。

#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <iterator>
#include <array>
#include <memory>
#include <stack>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<double,double>pdd;
typedef pair<ll,ll>pll;
int main(){
    int c,n,m,s,e;
    while(cin>>c>>n>>m>>s>>e,c+n+m+e+s){
        --s,--e;
        vector<vector<pii>>edge(n,vector<pii>());
        rep(i,m){
            int a,b,cost; cin>>a>>b>>cost;
            --a,--b;
            edge[a].push_back(pii(b,cost));
            edge[b].push_back(pii(a,cost));
        }
        typedef  pair<pii,int>piii;
        priority_queue<piii,vector<piii>,greater<piii>>que;
        vector<vector<int>>d(n,vector<int>(11,INF));
        que.push(piii(pii(0,c),s));
        d[s][c]=0;
        while(!que.empty()){
            piii now=que.top(); que.pop();
            if(d[now.second][now.first.second]<now.first.first)continue;
            for(int i=0; i<edge[now.second].size();i++){
                pii next=edge[now.second][i];
                if(d[next.first][now.first.second]>d[now.second][now.first.second]+next.second){
                    d[next.first][now.first.second]=d[now.second][now.first.second]+next.second;
                    que.push(piii(pii(d[next.first][now.first.second],now.first.second),next.first));
                }
                if(now.first.second>0){
                    if(d[next.first][now.first.second-1]>d[now.second][now.first.second]+(next.second)/2){
                        d[next.first][now.first.second-1]=now.first.first+(next.second)/2;
                        que.push(piii(pii(d[next.first][now.first.second-1],now.first.second-1),next.first));
                    }
                }
            }
        }
        int ans=INF;
        for(int i=0; i<=c; i++)cmin(ans,d[e][i]);
        cout<<ans<<endl;
    }
}