AOJ 2021: お姫様の危機 / Princess in Danger
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;
}