Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- import java.math.*;
- import java.util.concurrent.ConcurrentLinkedQueue;
- /**
- * Auto-generated code below aims at helping you parse
- * the standard input according to the problem statement.
- **/
- class Player {
- public static void main(String args[]) {
- Scanner in = new Scanner(System.in);
- int N = in.nextInt(); // the total number of nodes in the level, including the gateways
- int L = in.nextInt(); // the number of links
- int E = in.nextInt(); // the number of exit gateways
- boolean[][] edges = new boolean[N][N];
- boolean[] exits = new boolean[N];
- for (int i = 0; i < L; i++) {
- int N1 = in.nextInt(); // N1 and N2 defines a link between these nodes
- int N2 = in.nextInt();
- edges[N1][N2] = true;
- edges[N2][N1] = true;
- }
- for (int i = 0; i < E; i++) {
- int EI = in.nextInt(); // the index of a gateway node
- exits[EI] = true;
- }
- // game loop
- while (true) {
- int SI = in.nextInt(); // The index of the node on which the Skynet agent is positioned this turn
- ArrayList<ArrayList<Integer>> shortestPaths = getShortestPaths(N, SI, edges, exits);
- int[][] edgeCount = countEdges(N, shortestPaths);
- int maximum = -1;
- String edgeToCut = null;
- for(int N1 = 0; N1 < N; N1++) {
- for(int N2 = 0; N2 < N; N2++) {
- if(edgeCount[N1][N2] > maximum) {
- maximum = edgeCount[N1][N2];
- edgeToCut = N1+" "+N2;
- }
- }
- }
- // Example: 0 1 are the indices of the nodes you wish to sever the link between
- System.out.println(edgeToCut);
- }
- }
- private static ArrayList<ArrayList<Integer>> getShortestPaths(int N, int posIdx, boolean[][] edges, boolean[] exits) {
- //initialize data-structures for breadth-first-search
- ConcurrentLinkedQueue<Integer> visitingQueue = new ConcurrentLinkedQueue<Integer>();
- ArrayList<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>(N);
- for(int i = 0; i < N; i++) {
- paths.add(new ArrayList<Integer>());
- }
- ArrayList<ArrayList<Integer>> shortestPaths = new ArrayList<ArrayList<Integer>>();
- boolean[] visited = new boolean[N];
- int shortestLength = Integer.MAX_VALUE;
- //add first element
- paths.set(posIdx, new ArrayList<Integer>());
- visitingQueue.offer(posIdx);
- visited[posIdx] = true;
- //go through the queue in breadth-first-search
- while(!visitingQueue.isEmpty()) {
- int current = visitingQueue.poll();
- if(exits[current]) {
- shortestLength = Math.min(shortestLength, paths.get(current).size() + 1);
- }
- for(int i = 0; i < N; i++) {
- if(edges[i][current] && !visited[i]) {
- paths.set(i, new ArrayList<Integer>(paths.get(current)));
- paths.get(i).add(current);
- visitingQueue.offer(i);
- visited[i] = true;
- }
- }
- }
- for(int i = 0; i < N; i++) {
- if(exits[i] && paths.get(i).size() + 1 == shortestLength) {
- ArrayList<Integer> path = paths.get(i);
- path.add(i);
- shortestPaths.add(path);
- }
- }
- return shortestPaths;
- }
- private static int[][] countEdges(int N, ArrayList<ArrayList<Integer>> paths) {
- int[][] counts = new int[N][N];
- for(int i = 0; i < paths.size(); i++) {
- for(int j = 1; j < paths.get(i).size(); j++) {
- int N1 = paths.get(i).get(j-1);
- int N2 = paths.get(i).get(j);
- counts[N1][N2]++;
- counts[N2][N1]++;
- }
- }
- return counts;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement