Submission #653758

#	Time	Username	Problem	Language	Result	Execution time	Memory
653758		coderInTraining	Commuter Pass (JOI18_commuter_pass)	Java	0 / 100	151 ms	12808 KiB

commuter_pass

import java.util.*;

class Main {
    public static void main (String[]args) {
        Scanner scan = new Scanner (System.in);

        int nodeNumber = scan.nextInt();
        int edgeNumber = scan.nextInt();

        int startNode = scan.nextInt() - 1;
        int endNode = scan.nextInt() - 1;

        int bookStoreOne = scan.nextInt() - 1;
        int bookStoreTwo = scan.nextInt() - 1;

        Hashtable <Integer, ArrayList<Pair>> weightedGraph = new Hashtable <Integer, ArrayList<Pair>>();

        for (int i = 0; i < nodeNumber; i++) {
            weightedGraph.put(i, new ArrayList<Pair>());
        }

        for (int i = 0; i < edgeNumber; i++) {
            int firstNode = scan.nextInt() - 1;
            int secondNode = scan.nextInt() - 1;
            long edgeCost = scan.nextLong();

            ArrayList<Pair> temp = weightedGraph.get(firstNode);
            temp.add(new Pair(secondNode, edgeCost));
            weightedGraph.put(firstNode, temp);

            ArrayList<Pair> tempTwo = weightedGraph.get(secondNode);
            tempTwo.add(new Pair(firstNode, edgeCost));
            weightedGraph.put(secondNode, tempTwo);
        }

        long [] storeOneDistances = dijkstra(bookStoreOne, weightedGraph);
        long [] storeTwoDistances = dijkstra(bookStoreTwo, weightedGraph);
        long [] startDistances = dijkstra(startNode, weightedGraph);

        long initialValue = storeOneDistances[bookStoreTwo];

        /*
         * 
         */
        long [][][] dp = new long [nodeNumber][2][2];

        for (int i = 0; i < nodeNumber; i++) {
            for (int j = 0; j < 2; j++) {
                Arrays.fill(dp[i][j], Long.MAX_VALUE);
            }
        }

        dp[startNode][0][0] = 0;

        PriorityQueue <pqQuad> pq = new PriorityQueue <pqQuad>();
        pq.add(new pqQuad(startNode, 0, 0, 0));

        while (pq.isEmpty() == false) {
            pqQuad curQuad = pq.poll();

            int curNode = curQuad.node;
            int firstStage = curQuad.firstStage;
            int secondStage = curQuad.secondStage;
            long distance = curQuad.distanceFromStart;

            if (distance != dp[curNode][firstStage][secondStage]) {
                continue;
            }

            ArrayList<Pair> neighbors = weightedGraph.get(curNode);

            for (int i = 0; i < neighbors.size(); i++) {
                int neighborNode = neighbors.get(i).secondNode;
                long edgeCost = neighbors.get(i).edgeCost;

                // Connect to the start node
                if (dp[curNode][1][secondStage] > dp[curNode][firstStage][secondStage] + storeOneDistances[curNode]) {
                    dp[curNode][1][secondStage] = dp[curNode][firstStage][secondStage] + storeOneDistances[curNode];
                    pq.add(new pqQuad(curNode, 1, secondStage, dp[curNode][1][secondStage]));
                }

                // Connect to the end node
                if (dp[curNode][firstStage][1] > dp[curNode][firstStage][secondStage] + storeTwoDistances[curNode]) {
                    dp[curNode][firstStage][1] = dp[curNode][firstStage][secondStage] + storeTwoDistances[curNode];
                    pq.add(new pqQuad(curNode, firstStage, 1, dp[curNode][firstStage][1]));
                }

                // Move to the neighbor node
                if (dp[neighborNode][firstStage][secondStage] > dp[curNode][firstStage][secondStage] && startDistances[curNode] + edgeCost == startDistances[neighborNode]) {
                    dp[neighborNode][firstStage][secondStage] = dp[curNode][firstStage][secondStage];
                    pq.add(new pqQuad(neighborNode, firstStage, secondStage, dp[neighborNode][firstStage][secondStage]));
                }
            }
        }

        System.out.println(Math.min(storeOneDistances[bookStoreTwo], dp[endNode][1][1]));
    }

    private static class pqQuad implements Comparable<pqQuad> {
        int node;
        int firstStage;
        int secondStage;
        long distanceFromStart;

        public pqQuad (int node, int firstStage, int secondStage, long distanceFromStart) {
            this.node = node;
            this.firstStage = firstStage;
            this.secondStage = secondStage;
            this.distanceFromStart = distanceFromStart;
        }

        public int compareTo (pqQuad p) {
            if (distanceFromStart < p.distanceFromStart) {
                return (-1);
            }

            return (1);
        }
    }

    public static long[] dijkstra (int startNode, Hashtable <Integer, ArrayList<Pair>> weightedGraph) {
        int nodeNumber = weightedGraph.size();

        long [] distances = new long [nodeNumber];
        Arrays.fill(distances, Long.MAX_VALUE);
        distances[startNode] = 0;

        PriorityQueue <pqPair> pq = new PriorityQueue <pqPair>();
        pq.add(new pqPair(startNode, 0));

        while (pq.isEmpty() == false) {
            pqPair curPair = pq.poll();

            int curNode = curPair.node;
            ArrayList<Pair> temp = weightedGraph.get(curNode);

            for (int i = 0; i < temp.size(); i++) {
                int neighborNode = temp.get(i).secondNode;
                long edgeCost = temp.get(i).edgeCost;

                if (distances[neighborNode] > distances[curNode] + edgeCost) {
                    distances[neighborNode] = distances[curNode] + edgeCost;
                    pq.add(new pqPair(neighborNode, distances[neighborNode]));
                }
            }
        }

        return (distances);
    }

    private static class pqPair implements Comparable<pqPair> {
        int node;
        long distanceFromStart;

        public pqPair (int node, long distanceFromStart) {
            this.node = node;
            this.distanceFromStart = distanceFromStart;
        }

        public int compareTo (pqPair p) {
            if (distanceFromStart < p.distanceFromStart) {
                return (-1);
            }

            return (1);
        }
    }

    private static class Pair {
        int secondNode; 
        long edgeCost;

        public Pair (int secondNode, long edgeCost) {
            this.secondNode = secondNode;
            this.edgeCost = edgeCost;
        }
    }
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45