AOJ 2021: お姫様の危機をワーシャル-フロイト法で解く

問題

Princess in Danger | Aizu Online Judge

解法

まずは制限時間や冷凍庫位置を考えずに、ワーシャルフロイト法で任意の2点間の最小必要時間を出しておく。すると任意の2冷凍庫間の最小必要時間も出る。この後は冷凍庫間の移動だけを考えるので、それ以外の道は潰しておく。冷凍庫から冷凍庫の間で制限時間以上かかる移動はできないので、そういった道も潰しておく。潰し終わったら冷凍庫だけを含むグラフでワーシャルフロイトすれば、スタートの冷凍庫とゴールの冷凍庫の間でかかる最小必要時間が出る。この最小必要時間が制限時間より長い場合、それだけ凍結する必要があるので、最後に凍結する時間も足して出力する。

コード

import java.util.Scanner;

public class Main {
    private static final int MAX = 100000;
    private static int[][] map;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (true) {
            int cityNum = sc.nextInt();// 街の数
            int lim = sc.nextInt();// 制限時間
            int freezerNum = sc.nextInt();// 冷凍庫の数
            int edgeNum = sc.nextInt();// 道の数
            int S = sc.nextInt();// スタート
            int G = sc.nextInt();// ゴール
            if (cityNum == 0) {
                sc.close();
                break;
            }

            boolean[] isFreezer = new boolean[cityNum];
            isFreezer[S] = isFreezer[G] = true;
            for (int i = 0; i < freezerNum; i++) {
                isFreezer[sc.nextInt()] = true;
            }

            map = new int[cityNum][cityNum];
            for (int i = 0; i < edgeNum; i++) {
                int from = sc.nextInt();
                int to = sc.nextInt();
                int weight = sc.nextInt();
                map[from][to] = map[to][from] = weight;
            }

            // とりあえずワーシャルフロイト
            // ここでの目的は任意の2冷凍庫間の最小必要時間を出すこと
            WarshallFloyd();

            // 冷凍庫間で血液が死ぬ道は通れない
            for (int i = 0; i < cityNum; i++) {
                for (int j = 0; j < cityNum; j++) {
                    if (!isFreezer[i] || !isFreezer[j] || map[i][j] > lim) {
                        map[i][j] = MAX;
                    }
                }
            }

            // 自明に通れない道を消し去ったので
            // スタートからゴールへの最短経路を求めるためにワーシャルフロイト
            WarshallFloyd();

            if (map[S][G] >= MAX) {
                System.out.println("Help!");
            } else if (map[S][G] < lim) {
                System.out.println(map[S][G]);
            } else {
                System.out.println(2 * map[S][G] - lim);
            }
        }
    }

    static void WarshallFloyd() {
        // 任意の2点間の最小時間を入れる
        int n = map.length;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = MAX;
                }
            }
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i != j) {
                        map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                    }
                }
            }
        }
    }
}