AOJ 2021

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