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 <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <tuple>
#include <queue>

using namespace std;

#define int long long

class Solver {
};

signed main() {
	while (true) {
		int c, n, m, s, d;
		cin >> c >> n >> m >> s >> d;
		s--;
		d--;
		if (c == 0)break;

		vector<vector<vector<tuple<int, int, int>>>> graph(c + 1,
			vector<vector<tuple<int, int, int>>>(n));

		for (int i = 0; i < m; i++) {
			int a, b, f;
			cin >> a >> b >> f;
			a--;
			b--;
			for (int i = 0; i <= c; i++) {
				graph[i][a].emplace_back(make_tuple(i, b, f));
				graph[i][b].emplace_back(make_tuple(i, a, f));
				if (i < c) {
					graph[i][a].emplace_back(make_tuple(i + 1, b, f/2));
					graph[i][b].emplace_back(make_tuple(i + 1, a, f/2));
				}
			}
		}

		priority_queue<tuple<int, int, int>> que;
		vector<vector<int>> dist(c + 1, vector<int>(n, 1e9));
		que.emplace(make_tuple(0, s, 0));
		while (que.size() > 0) {
			int cnt = get<0>(que.top());
			int pos = get<1>(que.top());
			int distance = get<2>(que.top());
			que.pop();
			if (dist[cnt][pos] <= distance)continue;

			dist[cnt][pos] = distance;
			for (int i = 0; i < graph[cnt][pos].size(); i++) {
				int cnt_t = get<0>(graph[cnt][pos][i]);
				int pos_t = get<1>(graph[cnt][pos][i]);
				int distance_t = get<2>(graph[cnt][pos][i]);
				distance_t += distance;

				if (dist[cnt_t][pos_t] <= distance_t)continue;

				que.emplace(make_tuple(cnt_t, pos_t, distance_t));
			}
		}

		int res = 1e9;
		for (int i = 0; i <= c; i++)res = min(res, dist[i][d]);
		cout << res << endl;
	}
}

C++: #include<iostream>
#include<queue>

#define inf 1000000000

using namespace std;

int n,m;
int road[101][101];

class sint{
	public:
	int iti,now,tick;
	sint(){}
	sint(int a,int b,int c){iti=a;now=b;tick=c;}
	bool operator < (const sint &a)const{
		return now>a.now;
	}
};

int dike(int cick,int st,int en){
	priority_queue<sint> state;
	
	int sima[101][11];
	int visit[101][11];
	for(int i=0;i<101;i++){
		for(int j=0;j<11;j++){
			sima[i][j]=inf;
			visit[i][j]=0;
		}
	}
	state.push(sint(st,0,0));
	sima[st][0]=0;
	
	while(1){
		sint u=state.top();
		state.pop();
		
		visit[u.iti][u.tick]=1;
		if(u.iti==en){
			return u.now;
		}
		
		/*
		for(int i=0;i<cick;i++){
			for(int j=0;j<n;j++){
				printf("%d ",sima[j][i]);
			}puts("");
		}puts("");
		*/
		for(int i=1;i<=n;i++){
			if(road[u.iti][i]==inf || visit[i][u.tick]==1) continue;
			
			if(sima[u.iti][u.tick]+road[u.iti][i]<sima[i][u.tick]){
				sima[i][u.tick]=sima[u.iti][u.tick]+road[u.iti][i];
				state.push(sint(i,sima[i][u.tick],u.tick));
			}
			
			if(u.tick<cick){
				if(sima[u.iti][u.tick]+road[u.iti][i]/2 < sima[i][u.tick+1]){
					sima[i][u.tick+1]=sima[u.iti][u.tick]+road[u.iti][i]/2;
					state.push(sint(i,sima[i][u.tick+1],u.tick+1));
				}
			}
		}
	}
	
	return st;
}

int main(){
	while(1){
		int c,s,d;
		cin>>c>>n>>m>>s>>d;
		if(n==0)break;
		for(int i=0;i<101;i++){
			for(int j=0;j<101;j++){
				road[i][j]=inf;
			}
		}
		for(int i=0;i<m;i++){
			int a,b,e;
			cin>>a>>b>>e;
			road[a][b]=road[b][a]=e;
		}
		
		printf("%d\n",dike(c,s,d));
	}
}

C++: #include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define INF 100000000

struct edge {
	int to;
	int f;
	edge(int to_, int f_) {
		to = to_; f = f_;
	}
	edge(){}
};
struct status {
	int vertex;
	int cost;
	int c;
	status(int vertex_, int cost_, int c_) {
		vertex = vertex_; cost = cost_; c = c_;
	}
	status(){}
	bool operator<(const status & obj) const {
		if(this->c != obj.c)
			return this->c < obj.c;
		return this->cost > obj.cost;
	}
};

int main() {
	while(true) {
		int c, n, m, s, d;
		cin >> c >> n >> m >> s >> d;
		if(!(c || n || m || s || d))
			break;
		s--; d--;
		vector<vector<edge> > v(n);
		for(int i = 0; i < m; i++) {
			int a, b, f;
			cin >> a >> b >> f;
			a--; b--;
			v[a].push_back(edge(b,f));
			v[b].push_back(edge(a,f));
		}
		priority_queue<status> q;
		int cost[128][16];
		for(int i = 0; i < 128; i++)
			for(int j = 0; j < 16; j++)
				cost[i][j] = INF;
		q.push(status(s, 0, c));
		while(!q.empty()) {
			status cur;
			cur = q.top(); q.pop();

			if(cost[cur.vertex][cur.c] == INF) {
				cost[cur.vertex][cur.c] = cur.cost;
				for(int i = 0; i < v[cur.vertex].size(); i++) {
					if(cost[v[cur.vertex][i].to][cur.c] == INF) {
						q.push(status(v[cur.vertex][i].to, v[cur.vertex][i].f + cur.cost, cur.c));
					}
					if(cur.c > 0 && cost[v[cur.vertex][i].to][cur.c-1] == INF) {
						q.push(status(v[cur.vertex][i].to, v[cur.vertex][i].f / 2 + cur.cost, cur.c - 1));
					}
				}
			}
		}

		int ret = INF;
		for(int i = 0; i <= m; i++) {
			ret = min(ret, cost[d][i]);
		}
		cout << ret << endl;
	}
}

C++: //Solution for aoj:0212 Highway Express Bus
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
typedef pair<int, int>P;


struct S {
	int cost, to, num;
	S(int c, int t, int n) : cost(c), to(t), num(n){}
	bool operator>(const S &s) const {
		return cost > s.cost;
	}
};

const int INF = 1 << 30;
int c, n, m, s, d, ans;
int tocost[101][11];
vector<P> town[101];
priority_queue<S, vector<S>, greater<S> > pq;


void dijkstra(){
	while (!pq.empty()){
		S a = pq.top();
		pq.pop();
		for (int i = 0; i < town[a.to].size(); i++){
			int tt = town[a.to][i].first, cc = town[a.to][i].second;
			if (tocost[tt][a.num] > cc + a.cost){
				tocost[tt][a.num] = cc + a.cost;
				pq.push({ cc + a.cost, tt, a.num });
			}
			if (a.num>0&&tocost[tt][a.num-1] > cc/2 + a.cost){
				tocost[tt][a.num-1] = cc/2 + a.cost;
				pq.push({ cc/2 + a.cost, tt, a.num-1 });
			}
		}
	}
}
	int main(){
		while (cin >> c >> n >> m >> s >> d&&c&&n&&m&&s){
			for (int i = 0; i < 101; i++)
				fill(tocost[i], tocost[i] + 11, INF);
			tocost[s][c] = 0;
			ans = INF;
			while (pq.size())
				pq.pop();
			for (int i = 0; i < 101; i++)
				town[i].clear();
			for (int i = 0; i < m; i++){
				int a, b, c;
				cin >> a >> b >> c;
				town[a].push_back({ b, c });
				town[b].push_back({ a, c });
			}
			pq.push({ 0, s, c });
			dijkstra();
			for (int i = 0; i <= c; i++)
				ans = min(ans, tocost[d][i]);
			cout << ans << endl;
		}
		return 0;
	}