Go: package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

var scanner = bufio.NewScanner(os.Stdin)

const INF = 0x7FFFFFFF

var pass [][]int

func main() {
	for scanner.Scan() {
		pass = make([][]int, 200)
		for i := range pass {
			pass[i] = make([]int, 200)
		}
		buf := strings.Split(scanner.Text(), " ")
		c, _ := strconv.Atoi(buf[0])
		n, _ := strconv.Atoi(buf[1])
		m, _ := strconv.Atoi(buf[2])
		s, _ := strconv.Atoi(buf[3])
		d, _ := strconv.Atoi(buf[4])
		if c == 0 && n == 0 && m == 0 && s == 0 && d == 0 {
			break
		}
		s--
		d--
		for i := 0; i < 200; i++ {
			for j := 0; j < 200; j++ {
				pass[i][j] = INF
			}
		}
		for i := 0; i < 200; i++ {
			pass[i][i] = 0
		}
		for i := 0; i < m; i++ {
			scanner.Scan()
			buf_ := strings.Split(scanner.Text(), " ")
			a, _ := strconv.Atoi(buf_[0])
			b, _ := strconv.Atoi(buf_[1])
			f, _ := strconv.Atoi(buf_[2])
			a--
			b--
			pass[a][b] = f
			pass[b][a] = f
		}
		fmt.Println(dijkstra(s, d, c, n))
	}
}

func dijkstra(s, g, c, n int) float64 {
	d := make([][]float64, 200)
	used := make([][]bool, 200)
	for i := 0; i < 200; i++ {
		d[i] = make([]float64, 20)
		used[i] = make([]bool, 20)
	}
	for i := range d {
		for j := range d[i] {
			d[i][j] = INF
		}
	}
	d[s][c] = 0
	for {
		v := -1
		w := -1
		for u := 0; u < n; u++ {
			for i := 0; i < c+1; i++ {
				if !used[u][i] && (v == -1 || d[u][i] < d[v][w]) {
					v = u
					w = i
				}
			}
		}
		if v == -1 {
			break
		}
		used[v][w] = true
		for u := 0; u < n; u++ {
			d[u][w] = math.Min(d[u][w], d[v][w]+float64(pass[v][u]))
			if w-1 >= 0 && pass[v][u] != INF {
				d[u][w-1] = math.Min(d[u][w-1], d[v][w]+(float64(pass[v][u]/2.0)))
			}
		}
	}
	ret := float64(INF)
	for i := 0; i < c+1; i++ {
		ret = math.Min(ret, d[g][i])
	}
	return ret
}

C++: #include <stdio.h>
#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>

using namespace std;


// Highway Express Bus
// input 
// c n m s d : ????????? ????????° ???????????° ????????°??? ????????°???
// a b f : a??????b?????§f???

#define INF 1e+9
typedef pair<int, int> P;
struct edge{
	int to, cost; 
};

int c, n, m, s, d;
vector<edge> G[101];
int dp[11][101];	//????????????i???????????????j??°????????§???????°??????????


void dijkstra(int s,int a){		//????????????????????????????????°???a???????????????????????????
    priority_queue<P, vector<P>, greater<P> >Q;	//greater: ????´?????°????????????§??????????????¨????????????
    for(int i=0 ;i<n; i++) dp[a][i] = INF;
    dp[a][s] = 0;
    Q.push(P(0,s));	//??????????????°???
    
    while(!Q.empty()){
        P p=Q.top();  //p<cost, vertex>
        Q.pop();
        int v = p.second;
        
        if(dp[a][v] < p.first)continue;
        for(int i=0; i<G[v].size(); i++){
            edge e = G[v][i];	//v?????????????????´????????????{??°???????????????}
            int dm;
            if(a==0) dm = dp[a][v] + e.cost;	//???????????????????????¨???
            else dm = min(dp[a][v] + e.cost, dp[a-1][v] + e.cost/2);	//v?????????????????´?????§??????????????????
            															//??????????????§???????°????

            if(dp[a][e.to] > dm){
                dp[a][e.to] = dm;	//dm????????????????????????????????´??°
                Q.push(P(dp[a][e.to],e.to));	//?????\??????(?????????,?¬???°???)??§??\??????
            }
        }
    }
}


int main(){

	while(1){
		cin >> c >> n >> m >> s >> d;
		s--;
		d--;
		if(c==0) break;

		for(int i=0 ; i<m ; i++){
			int a, b, f;
			cin >> a >> b >> f;

			a--;
			b--;

			G[a].push_back((edge){b,f});	//??£??\?????????:a??????b?????§????????????
			G[b].push_back((edge){a,f});
		}

		int ans = INF;
	    for(int i=0;i<=c;i++){
    		dijkstra(s,i);
		}
        
	    cout << dp[c][d] << endl;
	     
	    for(int i=0;i<100;i++)G[i].clear();
	}

	return 0;
}

C++: #include <bits/stdc++.h>

using namespace std;

#define llong long long 
typedef pair<int, int> P;

typedef struct data{
	int now;
	int time;
	int dep;

	bool operator > (const data& right) const{
		return dep == right.dep ? time > right.time : dep > right.dep;
	}

}data;

int c, n, m, s, d;
vector<P> edges[101];
int cost[101][11];
priority_queue<data, vector<data>, greater<data> > q;

void solve(){
	data D;
	D.now = s;
	D.time = 0;
	D.dep = 0;
	q.push(D);

	while(!q.empty()){
		data nd = q.top(); q.pop();
		int nowp = nd.now;
		int nowtime = nd.time;
		int nowdep = nd.dep;

		if(cost[nowp][nowdep] < nowtime) continue;

		for(int i = 0; i < edges[nowp].size(); i++){
			P edge = edges[nowp][i];
			if(cost[edge.first][nowdep] > cost[nowp][nowdep] + edge.second){
				data in;
				in.now = edge.first;
				in.time = cost[nowp][nowdep] + edge.second;
				in.dep = nd.dep;
				cost[in.now][in.dep] = in.time;
				q.push(in);
			}

			if(nowdep < c){
				if(cost[edge.first][nowdep + 1] > cost[nowp][nowdep] + edge.second / 2){
					data in;
					in.now = edge.first;
					in.time = nowtime + (edge.second / 2);
					in.dep = nowdep + 1;
					cost[in.now][in.dep] = in.time;
					q.push(in);
				}			
			}

		}
	}

	return;
}

int main(){
	while(cin >> c >> n >> m >> s >> d, n){
		fill_n(*cost, 101 * 11, 99999999);
		for(int i = 0; i <= c; i++){
			cost[s][i] = 0;
		}
		for(int i = 0; i < m; i++){
			int n, to, cos;
			cin >> n >> to >> cos;
			edges[n].push_back(P(to, cos));
			edges[to].push_back(P(n, cos));
		}

		solve();

		// cout << cost[d][c] << endl;
		int minc = 999999999;
		for(int i = 0; i <= c; i++)
			minc = min(minc, cost[d][i]);
		cout << minc << endl;
		for(int i = 0; i < 101; i++){
			edges[i].clear();
		}
	}

	return 0;
}

C++: #include <map>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
int cost[101][11];
int main(){
	int c,N,m,s,d,i,j,k,x;
	for(;scanf("%d%d%d%d%d",&c,&N,&m,&s,&d),N;){
	fprintf(stderr,"%d %d %d %d %d\n",c,N,m,s,d);
		vector<map<int,int> >dist(N+1);
		memset(cost,99,sizeof(cost));
		for(k=0;k<m;k++){
			scanf("%d%d%d",&i,&j,&x);dist[i][j]=dist[j][i]=x;
			fprintf(stderr,"%d %d %d\n",i,j,x);
		}
		for(i=0;i<=c;i++)cost[s][i]=0;
		for(;~c;c--){
			vector<bool>used(N+1);
			for(;;){ //dijkstra
				int m=9999999;
				for(i=0;i<N;i++)if(!used[i]&&m>cost[i][c])m=cost[i][c];
				if(m==9999999)break;
				for(j=0;j<N;j++)if(m==cost[j][c]){
					map<int,int>::iterator it=dist[j].begin();
					for(used[j]=1;it!=dist[j].end();it++){
						if(cost[it->first][c]>it->second+cost[j][c])cost[it->first][c]=it->second+cost[j][c];
						if(c&&cost[it->first][c-1]>it->second/2+cost[j][c])cost[it->first][c-1]=it->second/2+cost[j][c];
					}
				}
			}
		}
		printf("%d\n",cost[d][0]);
	}
}