Codeforces Round #302 Div2 D: Destroying Roads

問題

codeforces.com

解法

kmjp.hatenablog.jp

まず二点間の最小距離を出しておく。nの最大値が3000なのでワーシャルフロイトをするとだから終わらない。辺の数の最大値が3000なので幅優先探索で求めても間に合う。

辺(i, j)を通るときの最小距離は以下のように書ける。

Math.min(dist[start][i] + dist[i][j] + dist[j][goal], dist[start][j] + dist[j][i] + dist[i][goal]);

S1->T1とS2->T2で辺(i,j)を共有しているパターンは上の式で出る。

コード

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	private final int DIST_MAX = 6000;

	public void solve() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();

		ArrayList<Integer>[] graph = new ArrayList[N];
		for (int i = 0; i < N; i++) {
			graph[i] = new ArrayList<>();
		}

		for (int i = 0; i < M; i++) {
			int from = sc.nextInt() - 1;
			int to = sc.nextInt() - 1;
			graph[from].add(to);
			graph[to].add(from);
		}
		int[] st = new int[2];
		int[] gl = new int[2];
		int[] limit = new int[2];
		for (int i = 0; i < 2; i++) {
			st[i] = sc.nextInt() - 1;
			gl[i] = sc.nextInt() - 1;
			limit[i] = sc.nextInt();
		}
		sc.close();

		// ワーシャルフロイトせずに幅優先探索
		int[][] dist = new int[N][N];
		for (int i = 0; i < N; i++) {
			Arrays.fill(dist[i], DIST_MAX);
		}
		for (int start = 0; start < N; start++) {
			dist[start][start] = 0;
			ArrayDeque<Integer> deque = new ArrayDeque<>();
			deque.add(start);
			while (!deque.isEmpty()) {
				int from = deque.poll();
				for (Integer to : graph[from]) {
					if (dist[start][to] > dist[start][from] + 1) {
						dist[start][to] = dist[start][from] + 1;
						deque.add(to);
					}
				}
			}
		}

		// そもそも最短距離が制限越えてたらアウト
		if (dist[st[0]][gl[0]] > limit[0] || dist[st[1]][gl[1]] > limit[1]) {
			System.out.println(-1);
			return;
		}

		int max = M - dist[st[0]][gl[0]] - dist[st[1]][gl[1]];
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				int[] di = new int[2];
				for (int k = 0; k < 2; k++) {
					int start = st[k];
					int goal = gl[k];
					di[k] = Math.min(dist[start][i] + dist[i][j] + dist[j][goal], dist[start][j] + dist[j][i]
							+ dist[i][goal]);
				}
				if (di[0] > limit[0] || di[1] > limit[1]) {
					continue;
				}
				max = Math.max(max, M - di[0] - di[1] + dist[i][j]);
			}
		}
		System.out.println(max);
	}

	public static void main(String[] args) {
		new Main().solve();
	}

}