読者です 読者をやめる 読者になる 読者になる

AOJ0212 Highway Express Bus

Dijkstra

//AOJ0212 Highway Express Bus
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;

#define INF 100000000
#define MAX_C 10
#define MAX_N 100
typedef pair<int,int> P;
typedef pair<int, P> PP;
int c,n,m,s,d;
int cost[MAX_N][MAX_C + 1];
bool used[MAX_N][MAX_C + 1];
int line[MAX_N][MAX_N];
typedef priority_queue<PP, vector<PP>, greater<PP> > que;
que dp;

int dijkstra(){
	while(!dp.empty()){
		PP p = dp.top(); dp.pop();
		P &x = p.second;
		if(used[x.second][x.first]) continue;
		used[x.second][x.first] = true;

		if(x.second == d){
			return p.first;
		}
		for(int i = 0;i < n;i++){
			if(cost[i][x.first] > p.first + line[x.second][i]){
				cost[i][x.first] = p.first + line[x.second][i];
				dp.push(PP(p.first + line[x.second][i], P(x.first, i)));
			}

			if(x.first > 0 && cost[i][x.first] > p.first + line[x.second][i] / 2){
				cost[i][x.first - 1] = p.first + line[x.second][i] / 2;
				dp.push(PP(p.first + line[x.second][i] / 2, P(x.first - 1, i)));
			}
		}
	}

}

int main(){
	int a,b,e;
	while(cin >> c >> n >> m >> s >> d, c){
		if(c == 0)break;
		s--;d--;
		for(int i = 0;i < MAX_N;i++){
			for(int j = 0; j < MAX_N;j++){
				line[i][j] = INF;
			}
		}

		for(int i = 0; i < m;i++){
			cin >> a >> b >> e;
			a--;b--;
			line[a][b] = e;
			line[b][a] = e;
		}
		for(int i = 0; i < MAX_N;i++){
			for(int j = 0; j  < MAX_C + 1;j++){
				cost[i][j] = INF;
				used[i][j] = false;
			}
		}
		dp = que();
		dp.push(PP(0, P(c, s)));
		cout << dijkstra() << endl;
		}
	return 0;
}