Go: package main

import (
	"container/heap"
	"fmt"
)

type Node struct {
	NowPosition          int
	DiscountTicketTCount int
	Amount               int
}

type PriorityQueueNode []*Node

func (pq PriorityQueueNode) Len() int {
	return len(pq)
}

func (pq PriorityQueueNode) Less(i, j int) bool {
	return pq[i].Amount < pq[j].Amount
}

func (pq PriorityQueueNode) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueueNode) Push(node interface{}) {
	*pq = append(*pq, node.(*Node))
}

func (pq *PriorityQueueNode) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

type Point struct {
	NextPoint int
	Fee       int
}

func main() {
	var c, n, m, s, d int
	var a, b, f int

	for {
		fmt.Scan(&c, &n, &m, &s, &d)
		if c == 0 && n == 0 && m == 0 && s == 0 && d == 0 {
			break
		}
		s--
		d--
		pointMap := make([][]Point, n)
		for i := 0; i < n; i++ {
			pointMap[i] = make([]Point, 0)
		}
		for i := 0; i < m; i++ {
			fmt.Scan(&a, &b, &f)
			a--
			b--
			pointMap[a] = append(pointMap[a], Point{NextPoint: b, Fee: f})
			pointMap[b] = append(pointMap[b], Point{NextPoint: a, Fee: f})
		}
		pq := make(PriorityQueueNode, 0)
		start := Node{NowPosition: s, DiscountTicketTCount: c, Amount: 0}
		heap.Push(&pq, &start)
		for len(pq) != 0 {
			now := heap.Pop(&pq).(*Node)
			if now.NowPosition == d {
				fmt.Println(now.Amount)
				break
			}
			for _, v := range pointMap[now.NowPosition] {
				next := &Node{v.NextPoint, now.DiscountTicketTCount, now.Amount + v.Fee}
				heap.Push(&pq, next)
				if now.DiscountTicketTCount > 0 {
					next = &Node{v.NextPoint, now.DiscountTicketTCount - 1, now.Amount + v.Fee/2}
					heap.Push(&pq, next)
				}
			}
		}
	}
}

C++: #include<iostream>
#include<queue>
#include<map>
#define MAX 10000000
#include<vector>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
struct edge{
	int cost,to;
};
typedef pair<int,int> p;
typedef pair<int,p> P;
//`Pbg@»ÝÌ@v
int main(){
	int tic,n,m,s,a,b,g,d[11][101],f;
	//d ticket place
	while(cin>>tic>>n>>m>>s>>g,tic||n||m||s||g){
		s--;g--;
		//tic `Pbg
		//n Ì
		//m ´Ì
		//s¨g
		vector<edge> v[101];
		rep(i,m){
			cin>>a>>b>>f;
			a--;b--;
			edge c;
			c.cost=f;
			c.to=b;v[a].push_back(c);
			c.to=a;v[b].push_back(c);
		}
		rep(i,tic+1)
		rep(j,n){
			if(j==s)
			d[i][j]=0;
			else
			d[i][j]=MAX;
		}
		int nowticket,nowplace,nowsum;
		priority_queue<P,vector<P>,greater<P> > que;
		P now;
		que.push(P(tic,p(s,0)));
		while(!que.empty()){
			now=que.top();
			que.pop();
			nowticket=now.first;
			nowplace=now.second.first;
			nowsum=now.second.second;
			if(d[nowticket][nowplace]<nowsum)
				continue;
			rep(i,(int)v[nowplace].size()){
				edge e=v[nowplace][i];
				if(nowticket>0){
					if(d[nowticket-1][e.to]>e.cost/2+nowsum){
						d[nowticket-1][e.to]=e.cost/2+nowsum;
						que.push(P(nowticket-1,p(e.to,d[nowticket-1][e.to])));
					}
				}
				if(d[nowticket][e.to]>e.cost+nowsum){
						d[nowticket][e.to]=e.cost+nowsum;
						que.push(P(nowticket,p(e.to,d[nowticket][e.to])));
				}
			}
		}
		int mi=100000000;
		rep(i,tic+1)
		mi=min(mi,d[i][g]);
		cout<<mi<<endl;
	}
	return 0;
}

C++: #include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<queue>
#include<vector>
using namespace std;

#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL

#define MAX_N 101
#define MAX_C 11

#define WHITE 0
#define GRAY 1
#define BLACK 2

typedef pair<int, int> pii;

struct edge { int to, c; };

vector<edge> G[MAX_N];
int color[MAX_N];
int	minc[MAX_C][MAX_N]; //dp?????????????????° ????????????id

void dijkstra(int C, int s) {
	priority_queue<pii, vector<pii>, greater<pii> >PQ; //minc v

	memset(color, WHITE, sizeof(color));
	fill(minc[C], minc[C + 1], INF);

	//?§????
	PQ.push(pii(0, s));
	minc[C][s] = 0;
	color[s] = GRAY;

	//PQ???????´????????????°
	while (!PQ.empty()) {
		//minc???????°??????¨??????????´????????????????
		pii p = PQ.top(); PQ.pop();

		int u = p.second;
		color[u] = BLACK;
		//????????§???????????°??????
		if (minc[C][u] < p.first) continue;

		//??£??\????????????????????¨????????????
		for (int j = 0; j < G[u].size(); j++) {
			edge e = G[u][j];
			if (color[e.to] == BLACK)continue;
			int m = (C == 0 ? minc[C][u] + e.c : min(minc[C][u] + e.c, minc[C - 1][u] + e.c / 2));
			if (minc[C][e.to] > m) {
				minc[C][e.to] = m;
				PQ.push(pii(minc[C][e.to], e.to));
				color[e.to] = GRAY;
			}
		}
	}
}

int main() {
	for (int C, n, m, s, d; cin >> C >> n >> m >> s >> d&&C;) {
		for (int i = 0; i < m; i++) {
			int a, b, f; scanf("%d%d%d", &a, &b, &f);
			edge e; e.to = b; e.c = f;
			G[a].push_back(e);
			e.to = a; e.c = f;
			G[b].push_back(e);
		}
		for (int i = 0; i <= C; i++) {
			dijkstra(i, s);
		}

		cout << minc[C][d] << endl;

		for (int i = 0; i <= n; i++) {
			G[i].clear();
		}
	}
	return 0;
}

C++: #include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<complex>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<functional>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>

using namespace std;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
#define INF 1e+8
#define rep(i,j) for(int i = 0; i < (j); i++)
#define reps(i,j,k) for(int i = j; i < k; i++)
typedef long long ll;
typedef unsigned long long ull;

struct edge{
	int to,cost,dis;
};

bool operator < (const edge &a,const edge &b){
    return a.cost > b.cost;
}

int main(){
	int c,n,m,s,g;
	while(scanf("%d%d%d%d%d",&c,&n,&m,&s,&g),n){
		int ans = 0;
		s--,g--;
		vector<edge> G[128];
		int d[128][32]={{}};
		rep(i,m){
			int a,b,cst;
			scanf("%d%d%d",&a,&b,&cst);
			a--,b--;
			edge in;
			in = {b,cst,-1};
			G[a].push_back(in);
			in = {a,cst,-1};
			G[b].push_back(in);
		}
		priority_queue<edge> PQ;
		edge start = {s,0,c};
		PQ.push(start);
		while(!PQ.empty()){
			edge pq = PQ.top();
			PQ.pop();
			if(d[pq.to][pq.dis]){
				d[pq.to][pq.dis]++;
				continue;
			}
			d[pq.to][pq.dis] = true;
			if(pq.to == g){
				printf("%d\n",pq.cost);
				break;
			}
			rep(u,G[pq.to].size()){
				edge next = {G[pq.to][u].to,pq.cost+G[pq.to][u].cost,pq.dis};
				PQ.push(next);
				if(pq.dis){
					next = {G[pq.to][u].to,pq.cost+G[pq.to][u].cost/2,pq.dis-1};
					PQ.push(next);
				}
			}
		}
	}
	return 0;
}