Submission #397015

#	Time	Username	Problem	Language	Result	Execution time	Memory
397015		SGSRainbowDragon	Commuter Pass (JOI18_commuter_pass)	Java	0 / 100	1069 ms	42540 KiB

commuter_pass

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

public class commuter_pass {

    static int[] distance;
    static ArrayList<Edge>[] edges;

    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());
        int 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;

        distance = new int[n];
        Arrays.fill(distance, -1);

        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 w = Integer.parseInt(st.nextToken());
            edges[one].add(new Edge(w, one, two));
            edges[two].add(new Edge(w, two, one));
        }

        distance[s] = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        for (Edge ed : edges[s])
        {
            pq.add(ed);
        }

        while (!pq.isEmpty() && distance[t] < 0)
        {
            Edge edge = pq.poll();

            if (distance[edge.endp] < 0)
            {
                distance[edge.endp] = distance[edge.startp] + edge.weight;

                for (Edge ed : edges[edge.endp])
                {
                    if (distance[ed.endp] < 0)
                    {
                        pq.add(ed);
                    }
                }
            }
        }

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

        // ArrayList<Integer> path = new ArrayList<Integer>();
        int pw = distance[t];
        int cur = t;
        // path.add(t+1);

        while (pw > 0)
        {
            for (Edge ed : edges[cur])
            {
                if (ed.weight == (distance[cur] - distance[ed.endp]))
                {
                    pw = pw - ed.weight;
                    ed.weight = 0;

                    for (Edge oe : edges[ed.endp])
                    {
                        if (oe.endp == cur)
                        {
                            oe.weight = 0;
                            break;
                        }
                    }

                    cur = ed.endp;
                    break;
                }
            }
        }

        // printPath(path);

        Arrays.fill(distance, -1);

        distance[u] = 0;

        pq.clear();
        for (Edge ed : edges[u])
        {
            pq.add(ed);
        }

        while (!pq.isEmpty() && distance[v] < 0)
        {
            Edge edge = pq.poll();

            if (distance[edge.endp] < 0)
            {
                distance[edge.endp] = distance[edge.startp] + edge.weight;

                for (Edge ed : edges[edge.endp])
                {
                    if (distance[ed.endp] < 0)
                    {
                        pq.add(ed);
                    }
                }
            }
        }

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

    static void printPath(ArrayList<Integer> path) {

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

    static class Edge implements Comparable<Edge> {

        int weight;
        int startp;
        int endp;

        public Edge (int w, int sp, int ep) {
            this.weight = w;
            this.startp = sp;
            this.endp = ep;
        }

        public int compareTo(Edge other) {
            return this.weight - other.weight;
        }
    }
}

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