AOJ 2021: お姫様の危機 / Princess in Danger

,

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2021

solution

Dijkstraやるだけ。$O((NM + MK) \log (NM))$。OJ上の時間制限$8$secは少し厳しいのでpushの回数を減らすなど多少頑張る必要がある。

implementation

#include <cstdio>
#include <queue>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

constexpr int inf = 1e9+7;
int main() {
    while (true) {
        // input
        int n, coldness_limit, machine_count, edge_count, start, goal; scanf("%d%d%d%d%d%d", &n, &coldness_limit, &machine_count, &edge_count, &start, &goal);
        if (n == 0) break;
        vector<bool> has_machine(n);
        repeat (i, machine_count) {
            int x; scanf("%d", &x);
            has_machine[x] = true;
        }
        vector<vector<pair<int, int> > > g(n);
        repeat (i, edge_count) {
            int x, y, t; scanf("%d%d%d", &x, &y, &t);
            if (coldness_limit < t) continue;
            g[x].emplace_back(y, t);
            g[y].emplace_back(x, t);
        }
        // solve
        auto dp = vectors(n, coldness_limit + 1, inf);
        priority_queue<tuple<int, int, int> > que;
        auto push = [&](int x, int coldness, int time) {
            if (dp[x][coldness] <= time) return;
            dp[x][coldness] = time;
            if (x == goal) return;
            que.emplace(time, x, coldness);
        };
        push(start, coldness_limit, 0);
        while (not que.empty()) {
            int time, x, coldness; tie(time, x, coldness) = que.top(); que.pop();
            if (dp[x][coldness] < time) continue;
            if (has_machine[x]) {
                for (int t = 0; coldness + t <= coldness_limit; ++ t) {
                    setmin(dp[x][coldness + t], time + t);
                }
            }
            for (auto edge : g[x]) {
                int y, dist; tie(y, dist) = edge;
                for (int t = 0; t + coldness <= coldness_limit; ++ t) {
                    if (0 <= coldness + t - dist) {
                        push(y, coldness + t - dist, time + t + dist);
                        if (has_machine[y]) break;
                    }
                    if (not has_machine[x]) break;
                }
            }
        }
        // output
        int result = inf;
        repeat (coldness, coldness_limit + 1) {
            setmin(result, dp[goal][coldness]);
        }
        if (result == inf) {
            printf("Help!\n");
        } else {
            printf("%d\n", result);
        }
    }
    return 0;
}