UVa-10269, ZOJ-1232 : Adventure of Super Mario

問題概要

重み付き有向グラフが与えられる。特殊な状況下ではワープが使える。ワープの使える回数には上限がある。最短路を求める問題。

解法

現在位置、ワープを使った回数を組にしてDijkstraする。

acceptされたコード

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

const int MAX_N = 100;
const int MAX_K = 10;
const int INF = 1<<29;

struct edge{
	int target, cost;
	edge(int target_, int cost_):target(target_), cost(cost_){}
};

int A, B, N, M, L, K;
vector<edge> graph[MAX_N];
bool can_go[MAX_N][MAX_N];

int dist[MAX_N];
int dist2[MAX_N][MAX_K+1];

struct state{
	int dist, cur, used;
	state(int dist_, int cur_, int used_ = -1):dist(dist_), cur(cur_), used(used_){}
};

bool operator<(const state& lhs, const state& rhs){
	return lhs.dist > rhs.dist;
}

void init(){
	scanf("%d%d%d%d%d",&A, &B, &M, &L, &K);
	N = A + B;

	for(int i=0; i<N; i++){
		graph[i].clear();
	}

	for(int i=0; i<M; i++){
		int a, b, c;
		scanf("%d%d%d",&a, &b, &c);
		a--; b--;
		graph[a].push_back(edge(b,c));
		graph[b].push_back(edge(a,c));
	}

	memset(can_go, false, sizeof(can_go));
}

int solve(){
	for(int i=0; i<N; i++){
		fill(dist, dist+N, INF);
		dist[i] = 0;
		priority_queue<state> que;
		que.push(state(0, i));
		while(!que.empty()){
			state tp = que.top(); que.pop();
			int cur = tp.cur, d = tp.dist;
			if(dist[cur] < d) continue;
			if(cur == i || cur < A){
				for(int j=0; j<(int)graph[cur].size(); j++){
					int v = graph[cur][j].target, nd = d + graph[cur][j].cost;
					if(nd <= L && nd < dist[v]){
						dist[v] = nd;
						que.push(state(nd, v));
					}
				}
			}
		}
		for(int j=0; j<N; j++){
			if(dist[j] < INF){
				can_go[i][j] = true;
			}
		}
	}

	for(int i=0; i<N; i++){
		fill(dist2[i], dist2[i]+K+1, INF);
	}
	priority_queue<state> que;
	que.push(state(0, N-1, 0));
	dist2[N-1][0] = 0;

	while(!que.empty()){
		state tp = que.top(); que.pop();
		int cur = tp.cur, d = tp.dist, used = tp.used;
		if(dist2[cur][used] < d) continue;

		//ワープ
		if(used < K)for(int i=0; i<N; i++)if(can_go[cur][i]){
			if(d < dist2[i][used+1]){
				dist2[i][used+1] = d;
				que.push(state(d, i, used+1));
			}
		}

		for(int i=0; i<(int)graph[cur].size(); i++){
			int v = graph[cur][i].target, nd = d + graph[cur][i].cost;
			if(nd < dist2[v][used]){
				dist2[v][used] = nd;
				que.push(state(nd, v, used));
			}
		}
	}

	return *min_element(dist2[0], dist2[0] + K+1);
}

int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		init();
		printf("%d\n", solve());
	}

	return 0;
}