AOJ 2021: Princess in Danger

pythonで粘ったがTLEから逃れられなかった。深いループの中で四則演算するとどうにもならない。

問題

問題はこちら

N個と都市間を結ぶM本の双方向道路があり、道路によって結ばれた都市は時間Tiで行き来できる。 今都市Aにいて、都市Hに冷凍された血液を冷凍されたまま運びたいのだが、血液はある程度時間がたつと溶けてしまう。 N個の都市のうちL個は冷凍施設を持っており、血液を再度冷凍することができる。はじめ血液は時間Mだけ溶けずにいることができ、冷凍施設では冷凍に使った時間分だけ血液の解けずにいられる時間が伸びる（ただし最大Mまで）。 これらの条件のもと都市Aから都市Hまで無事に血液を運ぶことができるかどうか、できるなら運ぶのにかかる最短の時間を答える。

解法

いくつか解き方があるようだが、ダイクストラを用いた方法とワーシャル・フロイドを用いた方法に分かれるようだ。自分はワーシャル・フロイドを用いた方法で解いた。

まずワーシャル・フロイドを適用して都市間の距離を計算する。大切なのは冷凍施設のある都市で、はじめ都市Aから出発し、距離M以下で都市Hに到達できる都市に行きつくまで、距離M以下の冷凍施設のある都市を巡っていけばいい。これもワーシャル・フロイドが適用でき、都市Aと冷凍施設のある都市間の移動時間、冷凍施設のある都市間の移動時間、冷凍施設のある都市と都市H間の移動時間を2次元配列に代入してワーシャルフロイドを行えば、都市Aと都市Hまでの最短時間を計算できる。あとはこの時間tがINF以上ならHelp!を、INF以下ならMを超えるかどうかチェックし、越えていたらt-Mを足し加えればいい（適当な都市で再冷凍を行ったことにする）。

#include <iostream>
#define REP(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) REP(i,0,a)
using namespace std;

const int INF = 1 << 28;
int N, M, L, K, A, H, x, y, t;
int d[101][101], dd[101][101], c[101];

int main(void){
    while (cin >> N >> M >> L >> K >> A >> H, N) {
        rep(i, 101) rep(j, 101) d[i][j] = dd[i][j] = INF;
        rep(i, L) cin >> c[i];
        rep(i, K) {
            cin >> x >> y >> t;
            d[x][y] = d[y][x] = t;
        }
        
        rep(k, N) rep(i, N) rep(j, N) d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
        
        rep(i, L) {
            dd[  0][i+1] = dd[i+1][  0] = (d[A][c[i]] <= M ? d[A][c[i]]:INF);
            dd[L+1][i+1] = dd[i+1][L+1] = (d[H][c[i]] <= M ? d[H][c[i]]:INF);
        }
        
        rep(i, L) rep(j, L) dd[i+1][j+1] = (d[c[i]][c[j]] <= M ? d[c[i]][c[j]]:INF);
        
        dd[0][L+1] = dd[L+1][0] = (d[A][H] <= M ? d[A][H]:INF);
        rep(k, L+2) rep(i, L+2) rep(j, L+2) dd[i][j] = min(dd[i][j], dd[i][k]+dd[k][j]);
        
        int time = dd[0][L+1];
        if (time < INF) cout << time + max(0, time-M) << endl;
        else cout << "Help!" << endl;
    }
    return 0;
}