srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

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