Untitled
unknown
java
2 years ago
4.9 kB
4
Indexable
import java.util.*; public class Main { public static void main(String[] args){ Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); Integer[][] timeData = new Integer[t][2]; Integer[] nodeNumbers = new Integer[t+1]; for (int i = 0; i < t; i++){ timeData[i][0] = scanner.nextInt(); timeData[i][1] = scanner.nextInt(); } for (int i = 0; i < t + 1; i++){ nodeNumbers[i] = i; } int e = scanner.nextInt(); Map<Integer,Node> setUpMap = new HashMap<>(); PriorityQueue<Node> nodes = new PriorityQueue<>(); for(Integer i = 0; i < e; i++){ Integer prev = scanner.nextInt(); nodeNumbers[prev] = 0; Integer next = scanner.nextInt(); nodeNumbers[next] = 0; if (!setUpMap.containsKey(prev)) { Node node = new Node(); node.setId(prev); node.setTime(timeData[prev-1][0]); node.addNext(next); setUpMap.put(prev, node); } else { Node node = setUpMap.get(prev); ArrayList<Integer> nextNodes = node.getNext(); if (!nextNodes.contains(next)){ node.addNext(next); } } if (!setUpMap.containsKey(next)){ Node node = new Node(); node.setId(next); node.setTime(timeData[next-1][0]); node.addPrev(prev); setUpMap.put(next, node); } else { Node node = setUpMap.get(next); ArrayList<Integer> prevNodes = node.getPrev(); if (!prevNodes.contains(prev)){ node.addPrev(prev); } } } for(int i = 1; i < t + 1; i++){ if (nodeNumbers[i] != 0){ Node node = new Node(); node.setId(i); node.setTime(timeData[i-1][0]); setUpMap.put(i, node); } } nodes = createQueue(setUpMap, t); int result = 0; while (!nodes.isEmpty()){ Node node = nodes.poll(); setUpMap.remove(node.id); ArrayList<Integer> nextNodes = node.getNext(); for(Integer nodeNumber : nextNodes){ Node fromMap = setUpMap.get(nodeNumber); ArrayList<Integer> prevNodes = fromMap.getPrev(); int index = prevNodes.indexOf(node.id); if (index > -1){ prevNodes.remove(index); } fromMap.setPrev(prevNodes); setUpMap.put(fromMap.id, fromMap); } //System.out.println(node.id); if (result < timeData[node.id - 1][0]){ int diff = timeData[node.id - 1][0] - result; result += diff + timeData[node.id - 1][1]; } else { result += timeData[node.id - 1][1]; } nodes = createQueue(setUpMap, t); } System.out.println(result); } public static PriorityQueue<Node> createQueue(Map<Integer,Node> hashMap, int e){ PriorityQueue<Node> nodePriorityQueue = new PriorityQueue<>(); for (int i = 1; i <= e; i++){ if (hashMap.get(i) != null){ nodePriorityQueue.offer(hashMap.get(i)); } } return nodePriorityQueue; } } class Node implements Comparable<Node>{ int id; ArrayList<Integer> prev = new ArrayList<>(); ArrayList<Integer> next = new ArrayList<>(); Integer time; public Node(int id, ArrayList<Integer> prev, ArrayList<Integer> next, Integer time) { this.id = id; this.prev = prev; this.next = next; this.time = time; } @Override public int compareTo(Node other) { // sort based on the smallest t value int r = Integer.compare(this.prev.size(), other.prev.size()); return r == 0 ? Integer.compare(this.time, other.time) : r; } public void addPrev(Integer prevInt){ prev.add(prevInt); } public void addNext(Integer nextInt){ next.add(nextInt); } public Node() { } public int getId() { return id; } public void setId(int id) { this.id = id; } public ArrayList<Integer> getPrev() { return prev; } public void setPrev(ArrayList<Integer> prev) { this.prev = prev; } public ArrayList<Integer> getNext() { return next; } public void setNext(ArrayList<Integer> next) { this.next = next; } public Integer getTime() { return time; } public void setTime(Integer time) { this.time = time; } }
Editor is loading...