AOJ 0212 - Highway Express Bus

二つの状態で管理するdijkstra法．
何枚使ったかとどこにいるかを保持しておく．

#include<iostream>
#include<algorithm>

const int INF = 1 << 24;
int ticket, V, E, start, goal;
//d[i][j]: i枚使ったんだよー
int d[11][101], used[11][101], cost[101][101];

int dijkstra(int s){
	for(int i=0;i<11;i++){
		std::fill(d[i], d[i]+101, INF);
		std::fill(used[i], used[i]+101, 0);
	}

	d[0][s] = 0;

	while(true){
		int u = -1, v;
		for(int i=0;i<=ticket;i++){
			for(int j=1;j<=V;j++){
				if(!used[i][j] && (u == -1 || d[i][j] < d[u][v])){
					u = i;
					v = j;
				}
			}
		}

		if(u == -1)break;
		used[u][v] = 1;

		for(int j=1;j<=V;j++){
			d[u][j] = std::min(d[u][j], d[u][v] + cost[v][j]);
			if(u+1 <= ticket){
				d[u+1][j] = std::min(d[u+1][j], d[u][v] + cost[v][j] / 2);
			}
		}
	}
	
}

int main(){
	while(std::cin >> ticket >> V >> E >> start >> goal, V){
		for(int i=1;i<=100;i++){
			for(int j=1;j<=100;j++){
				cost[i][j] = INF;
			}
		}
		for(int i=0;i<E;i++){
			int a, b, f;
			std::cin >> a >> b >> f;
			cost[a][b] = cost[b][a] = f;
		}
		dijkstra(start);
		int res = INF;
		for(int i=0;i<=ticket;i++){
			res = std::min(res, d[i][goal]);
		}
		std::cout << res << std::endl;
	}
}