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<queue>
#include<string.h>
using namespace std;

const int INF = 1<<30;

struct Node{
  int use,to,weight;
  Node() {;}
  Node(int use,int to,int weight) : use(use), to(to), weight(weight) {;}
};
bool operator<(const Node &e,const Node &f) {
  return e.weight > f.weight;
}

int dist[110][110];
bool visit[110];
int dist2[110][110];

int main() {
  int c,n,m,s,d,a,b,f;
    while(cin>>c>>n>>m>>s>>d, c|n|m|s|d) {
      s--,d--;

      for(int i=0; i<110; ++i) {
	for(int j=0; j<110; ++j) {
	  dist[i][j] = INF;
	}
	visit[i] = false;
      }

      for(int i=0; i<110; ++i)
	for(int j=0; j<110; ++j)
	  dist2[i][j] = INF;

      for(int i=0; i<m; ++i) {
	cin>>a>>b>>f;
	a--,b--;
	dist[a][b] = f;
	dist[b][a] = f;
      }

      priority_queue<Node> Q;
      Q.push(Node(0,s,0));
      visit[s] = true;
      while(!Q.empty()) {
	Node now = Q.top(); Q.pop();

	visit[now.to] = true;
	for(int i=0; i<n; ++i) {
	  if(!visit[i] && dist[now.to][i] != INF) {
	    if(dist2[now.use+1][i]
	       > now.weight + dist[now.to][i]/2 && now.use < c) {
	      dist2[now.use+1][i] = now.weight + dist[now.to][i]/2;
	      Q.push(Node(now.use+1, i, dist2[now.use+1][i]));
	    }
	    if(dist2[now.use][i]
	       > now.weight + dist[now.to][i]) {
	      dist2[now.use][i] = now.weight + dist[now.to][i];
	      Q.push(Node(now.use, i, dist2[now.use][i]));
	    }
	  }
	}
      }
      int sum = INF;
      for(int i=0; i<=c; ++i) {
	//cout<<dist2[i][d]<<" : "<<i<<endl;
	sum = min(sum , dist2[i][d]);
      }
      cout<<sum<<endl;
    }
}

C++: #include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

//int dy[]={0, 0, 1, -1, 0};
//int dx[]={1, -1, 0, 0, 0};

struct edge{
  int to, cost;
};

int c, n, m, start, goal;
vector<edge> v[105];	       
vector<int> d(105, INF);
priority_queue<P> q, q2;

int dijkstra(int s){
  vector<int> d2(105, INF);

  d[s]=0;
  q.push(P(0, s));
  while(!q.empty()){
    int u=q.top().second;
    q.pop();
    
    REP(i, v[u].size()){
      int to=v[u][i].to;
      int cost=v[u][i].cost;
      if(d[to]>d[u]+cost){
	d[to]=d[u]+cost;
	q.push(P(-d[to], to));
      }
      if(d2[to]>d[u]+cost/2){
	d2[to]=d[u]+cost/2;
	q2.push(P(-d2[to], to));
      }
    }
  }
  
  d=d2;
  q=q2;
  while(!q2.empty()) q2.pop();
}

int main(){
  while(1){
    scanf("%d%d%d%d%d", &c, &n, &m, &start, &goal);
    start--; goal--;
    if(c==0) return 0;
    
    REP(i, m){
      int from, to, f;
      scanf("%d%d%d", &from, &to, &f);
      from--; to--;
      v[to].push_back((edge){from, f});
      v[from].push_back((edge){to, f});
    }

    REP(i, c+1){
      dijkstra(start);
    }

    printf("%d\n", d[goal]);

    REP(i, 105){
      v[i].erase(v[i].begin(), v[i].end());
      d[i]=INF;
    }
  }
}

C++: #include <bits/stdc++.h>
#define INF (1<<29)
#define all(c) (c).begin(),(c).end()
#define pb(c) push_back(c)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> PP;

int dis[111][111];
int c, n, m, s, d;
int next[111][11];

void dfs(int cur, int sum, int cost){
  if(next[cur][sum] < cost) return;
  next[cur][sum] = cost;
  for(int i = 0; i < n; i++){
    if(dis[cur][i] == (1<<29)) continue;
    if(sum > 0) dfs(i, sum-1, cost+(dis[cur][i]/2));
    dfs(i, sum, cost+dis[cur][i]);
  }
}

int main(){
  ios::sync_with_stdio(false);

  while(cin >> c >> n >> m >> s >> d && (c||n||m||s||d)){

    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        dis[i][j] = next[i][j] = (1<<29);
      }
    }

    for(int i = 0; i < m; i++){
      int a, b, f;
      cin >> a >> b >> f;
      a--; b--;
      dis[a][b] = f;
      dis[b][a] = f;
    }

    dfs(s-1,c,0);
    int ans = (1<<29);
    for(int i =0; i < c; i++){
      ans = min(ans, next[d-1][i]);
    }
    cout << ans << endl;
  }


}