http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2021&lang=jp
は?これも難しくないか?
普通にO(MN)頂点O(MN^2)辺のグラフでダイクストラすればいいんですが、これだと若干重くないか?ということで、O(N^3)解法にしました。
Aから中継点を数カ所挟んでHに行くわけですが、その間、距離M以上は移動できません。
逆にこの条件さえ満たしていれば、AからHへの最短距離をdとして、答えはmax(d, 2d-M)です。
なぜかというと、d<=Mの時は答えがdになることは言うまでもなく、d>Mのとき、d-Mだけ補給しなければなりません。よって答えの下界はd+(d-M)=2d-Mになるわけですが、これは達成できます。max(d,2d-M)はd<=Mのとき、d>Mのときで答えと一致します。
あとはワーシャルフロイドを2回やればいいです。1回目は、全頂点間で、2回目はAとHと中継点で長さがMより大きい辺を除いたグラフで行います。
しかしダイクストラより遅くてかなしぃ。
int N, M, L, K, A, H; bool blood[110]; ll d[110][110]; ll e[110][110]; void solve() { while(true) { cin >> N >> M >> L >> K >> A >> H; debug(K); if(N == 0) break; memset(blood, 0, sizeof(blood)); rep(i, 0, L) { int a; cin >> a; blood[a] = true; } blood[A] = true; blood[H] = true; rep(i, 0, N) { rep(j, 0, N) { d[i][j] = inf; e[i][j] = inf; } } while(K--) { int a, b; ll c; cin >> a >> b >> c; MIN(d[a][b], c); MIN(d[b][a], c); } rep(k, 0, N) { rep(i, 0, N) { rep(j, 0, N) { MIN(d[i][j], d[i][k] + d[k][j]); } } } rep(i, 0, N) { rep(j, 0, N) { if(blood[i] && blood[j] && d[i][j] <= M) { e[i][j] = d[i][j]; } } } rep(k, 0, N) { rep(i, 0, N) { rep(j, 0, N) { MIN(e[i][j], e[i][k] + e[k][j]); } } } if(e[A][H] == inf) { cout << "Help!\n"; } else { cout << max(2 * e[A][H] - M, e[A][H]) << "\n"; } } }