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; }