Submission #397029

#	Time	Username	Problem	Language	Result	Execution time	Memory
397029		SGSRainbowDragon	Commuter Pass (JOI18_commuter_pass)	Java	0 / 100	2094 ms	36432 KiB

commuter_pass

import java.util.*;
import java.io.*;

public class commuter_pass {

    static ArrayList<Edge>[] edges;
    static Node[] nodes;
    static int n;
    static ArrayList<Integer> path;

    public static void main(String[] args) throws IOException{

        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader input = new BufferedReader(new FileReader("cp.in"));
        // PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("cp.out")));

        StringTokenizer st = new StringTokenizer(input.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(input.readLine());
        int s = Integer.parseInt(st.nextToken()) - 1;
        int t = Integer.parseInt(st.nextToken()) - 1;

        st = new StringTokenizer(input.readLine());
        int u = Integer.parseInt(st.nextToken()) - 1;
        int v = Integer.parseInt(st.nextToken()) - 1;

        nodes = new Node[n];

        edges = new ArrayList[n];
        for (int i = 0; i < n; i++)
        {
            edges[i] = new ArrayList<Edge>();
        }

        for (int i = 0; i < m; i++)
        {
            st = new StringTokenizer(input.readLine());
            int one = Integer.parseInt(st.nextToken()) - 1;
            int two = Integer.parseInt(st.nextToken()) - 1;
            int weight = Integer.parseInt(st.nextToken());
            Edge edge = new Edge(weight, one, two);
            edges[one].add(edge);
            edges[two].add(edge);
        }

        getShortestPath(s, t);

        // System.out.println(distance[t]);

        getPath(s, t);

        // printPath();

        getShortestPath(u, v);

        System.out.println(nodes[v].distance);
    }

    static void getShortestPath(int start, int end) {

        for (int i = 0; i < n; i++)
        {
            nodes[i] = new Node(i, Long.MAX_VALUE);
        }

        int current = start;
        nodes[current].distance = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(nodes[current]);


        while (!pq.isEmpty() && !nodes[end].visited) {
            Node currentNode = pq.poll();
            current = currentNode.index;

            for (Edge edge : edges[current])
            {
                int other = edge.getOther(current);
                if (nodes[other].distance > (nodes[current].distance + edge.weight))
                {
                    pq.remove(nodes[other]);
                    nodes[other].distance = nodes[current].distance + edge.weight;
                    pq.add(nodes[other]);
                }
            }
        }
    }

    static void getPath(int start, int end) {

        path = new ArrayList<>();

        long pw = nodes[end].distance;
        int current = end;
        path.add(end+1);

        while (pw > 0)
        {
            for (Edge edge : edges[current])
            {
                int other = edge.getOther(current);
                if (edge.weight == (nodes[current].distance - nodes[other].distance))
                {
                    pw = pw - edge.weight;
                    edge.weight = 0;
                    current = other;
                    path.add(current+1);
                    break;
                }
            }
        }
    }

    static void printPath() {

        for (int i : path) {
            System.out.print(i + " - ");
        }
        System.out.println();
    }

    static class Edge {

        int weight;
        int one;
        int two;

        public Edge (int weight, int one, int two) {
            this.weight = weight;
            this.one = one;
            this.two = two;
        }

        public int getOther (int current) {
            return current == this.one ? this.two : this.one;
        }
    }

    static class Node implements Comparable<Node> {

        int index;
        long distance;
        boolean visited;

        public Node (int index, long distance) {
            this.index = index;
            this.distance = distance;
            this.visited = false;
        }

        public int compareTo(Node other) {
            if (this.distance < other.distance)
            {
                return -1;
            }
            else if (this.distance > other.distance)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }
    }
}

Compilation message (stderr)

Note: commuter_pass.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

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