AOJ_0212 Highway Express Bus

問題
解法
ダイクストラ法を使って、ああでもないこうでもないとやっている
うちになぜか解けてしまったのでよくわからない。
動的計画法も使っているような気がする…だけかもしれない。
割引券の枚数に対する最短距離？みたいなのを計算していく？というような？
ことをやっているのでは？ないでしょうか？

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> CP; //割引券の枚数と現在位置
typedef pair<int, CP> D; //最短距離とCP
const int INF = 1 << 30;
const int MAX_N = 100;
int C, N, M, S, G;
int rail[MAX_N][MAX_N];

int dijk(){
	priority_queue<D> Q;
	//d[i][j] := jに残り割引券i枚以上で着いたときの最短距離
	int d[C+1][N];
	for(int i = 0; i <= C; i++)
		for(int j = 0; j < N; j++)
			d[i][j] = INF;
	Q.push(D(0, CP(C, S)));
	while(!Q.empty()){
		D pos = Q.top(); Q.pop();
		int dis = pos.first, cn = pos.second.first, p = pos.second.second;
		if(!(d[cn][p] > dis)) continue;
		//最短距離を更新
		for(int i = 0; i <= cn; i++)
			d[i][p] = min(dis, d[i][p]);
		for(int i = 0; i < N; i++){
			if(rail[i][p] == INF) continue;
			if(dis + rail[i][p] < d[cn][i])
				Q.push(D(dis + rail[i][p], CP(cn, i)));
			if(cn != 0 && dis + rail[i][p]/2 < d[cn-1][i])
				Q.push(D(dis + rail[i][p] / 2, CP(cn - 1, i)));
		}
	}
	int ans = INF;
	for(int i = 0; i <= C; i++)
		ans = min(ans, d[i][G]);
	return  ans;
}
int main(){
	while(scanf("%d %d %d %d %d", &C,&N,&M,&S,&G) && C){
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++)
				rail[i][j] = INF;
		S--; G--;
		for(int i = 0; i < M; i++){
			int a, b, f;
			scanf("%d %d %d", &a, &b, &f);
			a--; b--;
			rail[a][b] = f; rail[b][a] = f;
		}
		printf("%d\n", dijk());
	}
	return 0;
}