Untitled

mail@pastecode.io avatar
unknown
java
a year ago
4.9 kB
1
Indexable
Never
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;
    }
}