aoj 2021 - Princess in Danger
問題概要
スタートからゴールまで冷凍されたものを溶かさずにもっていけるかを求める問題。冷凍されたものは最大でm時間保存することができ、時間がたつと解ける。与えらた条件にある頂点で氷を冷凍することができる。溶かさずにゴールまで行く最短時間を求める問題。
解法
拡張ダイクストラで解いた。頂点の状態に番号だけでなく、その頂点にいるときの溶けるまでの残り時間を持たせる。こうすることで、dist[u][t] := 現在の頂点がuで残り時間がtの時の時の最短時間 とき、ダイクストラで値を更新していくことができる。また、冷凍できる頂点での処理は、まったく冷凍しない場合から、完全に冷凍する状態のすべてを試せばいい。
ミス
拡張ダイクストラの練習になった。
コード
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <cstdio> #include <tuple> using namespace std; typedef long long ll; typedef tuple<int, int, int> tup; #define rep(i,n) for(int i=0;i<(n);i++) const int INF = 1e9; int n, m, l, k, a, h; bool reitou[110]; vector<pair<int, int> > G[110]; //dist[u][t] := 現在の頂点がuで残り時間がtの時の時の最短時間 int dist[110][110]; void dijkstra(int start){ rep(i, 110)rep(j, 110){ dist[i][j] = INF; } priority_queue<tup, vector<tup>, greater<tup> > q; q.push(make_tuple(0, start, m));//時間 現在の頂点 残り時間 while(!q.empty()){ int cost, u, t;//今までにかかった時間 現在の頂点 解けるまでの残り時間 tie(cost, u, t) = q.top(); q.pop(); if(dist[u][t] < cost) continue; for (auto tmp : G[u]){ int v = tmp.first, time = tmp.second;//隣接する頂点 その頂点まで行く時間 if(reitou[u]){//冷やせる for (int i = 0; i <= m; ++i){//i分間体力を回復 if(t + i > m) break;//無駄に休む必要はない if(t + i - time < 0) continue; if(cost + i + time < dist[v][t + i - time]){//最短時間更新 dist[v][t + i - time] = cost + i + time; q.push(make_tuple(dist[v][t + i - time], v, t + i - time)); } } }else{ if(t - time < 0) continue; if(cost + time < dist[v][t - time]){//最短時間更新 dist[v][t - time] = cost + time; q.push(make_tuple(dist[v][t - time], v, t - time)); } } } } } int main(void){ while(1){ cin >> n >> m >> l >> k >> a >> h; if(n == 0) return 0; rep(i, 110) reitou[i] = false; rep(i, 110) G[i].erase(G[i].begin(), G[i].end()); rep(i, l){ int tmp; cin >> tmp; reitou[tmp] = true; } rep(i, k){ int u, v, c; cin >> u >> v >> c; G[u].push_back(make_pair(v, c)); G[v].push_back(make_pair(u, c)); } dijkstra(a); int ans = INF; for (int i = 0; i <= m; ++i){ ans = min(ans, dist[h][i]); } if(ans == INF){ printf("Help!\n"); }else{ printf("%d\n", ans); } } return 0; }