TopCoder SRM 699 Div2 Hard: FromToDivisibleDiv2
問題
N 個の頂点があり、各頂点に 1 から N の番号が振られています。各 a[i] と b[i] について、 a[i] の倍数の全ての頂点から b[i] の倍数の全ての頂点へ距離 1 の有向辺を張ります。S から T への距離を求めてください。
解法
条件より 距離が 500 以上になることはないので、距離 500 の BFS をやるイメージで行きます。辺 x から辺 y について、b[x] と a[y] の LCM が N 以下であれば移動できると考えると簡単なグラフにできます。
コード
import java.util.ArrayDeque; import java.util.ArrayList; public class FromToDivisibleDiv2 { // 最大公約数 private static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); } // 最小公倍数 static long lcm(long a, long b) { return a * b / gcd(a, b); } final int INF = Integer.MAX_VALUE / 2; public int shortest(int N, int S, int T, int[] a, int[] b) { int M = a.length; ArrayList<Integer> cur = new ArrayList<>(); ArrayList<Integer> next = new ArrayList<>(); ArrayDeque<int[]> edges = new ArrayDeque<>(); for (int i = 0; i < M; i++) { if (S % a[i] == 0 && T % b[i] == 0) return 1; if (S % a[i] == 0) cur.add(b[i]); else edges.add(new int[]{a[i], b[i]}); } for (int d = 2; d <= 500; d++) { next.clear(); int s = edges.size(); for (int i = 0; i < s; i++) { int[] edge = edges.pollFirst(); boolean used = false; for (int v : cur) { if (lcm(v, edge[0]) <= N) { used = true; if (T % edge[1] == 0) return d; next.add(edge[1]); break; } } if (!used) edges.addLast(edge); } ArrayList<Integer> tmp = cur; cur = next; next = tmp; } return -1; } }