PG Battle2019解き直し～その4～

こちらの記事でPGBattleの第三問を解きなおしてみたのですが、コメント欄にてダイキストラ法というものがあると知り、この問題用に最適化して書いて再挑戦しました。
なかなか手を付けるまで時間がかかってしまいました・・・

入力の部分までは変わらず、その後の処理を大きく変更しました。

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {

	public static void main(String[] args) {
		HashMap<Integer, HashSet<Integer>> ballRouteMap = new HashMap<>();

		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int n = sc.nextInt();
		int m = sc.nextInt();

		IntStream.rangeClosed(0, n).forEach(i -> ballRouteMap.put(i, new HashSet<>()));

		for (int i = 1; i <= m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			ballRouteMap.get(b).add(a);
		}
		// 入力完了
		boolean canReturn[] = new boolean[n + 1];
		Arrays.fill(canReturn, false);

		canReturn[0] = true;
		HashSet<Integer> beforePlayers = new HashSet<>();
		beforePlayers.add(0);

		for (int i = 1; i <= 3; i++) {
			HashSet<Integer> players = new HashSet<>();
			for (int beforePlayer : beforePlayers) {
				for (int player : ballRouteMap.get(beforePlayer)) {
					canReturn[player] = true;
					players.add(player);
				}
			}
			beforePlayers = players;
		}

		for (int i = 1; i <= n; i++) {
			System.out.println(canReturn[i] ? "Yes" : "No");
		}
	}

}

はじめにcanReturn[]で返却可能かどうかの配列を用意し、高橋くんから逆に3経路たどった結果辿り着かなかった点についてはfalseのまま返すという風に変更しました。
ダイキストラ法から今回用に限定的にアレンジしたような感じになってしまいましたが・・・

結果、性能は1615msに改善しました！！
入力部分の処理は変更していないので、そこ次第でもう少しはやくなりそう・・・？
ぱっと思いつくのはballRouteMapにHashSet<>()をnewしまくっている部分。不要なnewをなくしてみました。

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {

	public static void main(String[] args) {
		HashMap<Integer, HashSet<Integer>> ballRouteMap = new HashMap<>();

		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int n = sc.nextInt();
		int m = sc.nextInt();

		for (int i = 1; i <= m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			if (!ballRouteMap.containsKey(b)) {
				ballRouteMap.put(b, new HashSet<>());
			}
			ballRouteMap.get(b).add(a);
		}
		// 入力完了
		boolean canReturn[] = new boolean[n + 1];
		Arrays.fill(canReturn, false);

		canReturn[0] = true;
		HashSet<Integer> beforePlayers = new HashSet<>();
		beforePlayers.add(0);

		for (int i = 1; i <= 3; i++) {
			HashSet<Integer> players = new HashSet<>();
			for (int beforePlayer : beforePlayers) {
				if (ballRouteMap.containsKey(beforePlayer)) {
					for (int player : ballRouteMap.get(beforePlayer)) {
						canReturn[player] = true;
						players.add(player);
					}
				}
			}
			beforePlayers = players;
		}

		for (int i = 1; i <= n; i++) {
			System.out.println(canReturn[i] ? "Yes" : "No");
		}
	}

}

結果、1484msまでさらに改善しました！
入力の部分も2次元配列使った方がはやいんでしょうね。。Collections系はリッチな分性能には直結しそうです。
HashSetもStackで代替できる部分もありそうなので、そちらも使えばちょっとは早くなる・・・のかな？

では今回は以上です！！コメントいただき、ありがとうございました！^^