Submission #857388

#	Time	Username	Problem	Language	Result	Execution time	Memory
857388		Oz121	Commuter Pass (JOI18_commuter_pass)	Java	100 / 100	994 ms	71564 KiB

commuter_pass

import java.io.*;
import java.util.*;
public class commuter_pass {
    public static int num; public static int m; public static long ans;
    public static int s; public static int t; public static int u; public static int v;

    public static long[] udis; public static long[] vdis;
    public static long[] dpU; public static long[] dpV; //The distances from U to node where node is end point of the current path (also the shortest by djikstra) from s to node

    public static ArrayList<ArrayList<Pair>> adj;
    public static void main(String[] args) throws IOException {
        BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer l1 = new StringTokenizer(scan.readLine());
        num = Integer.parseInt(l1.nextToken()); m = Integer.parseInt(l1.nextToken());

        StringTokenizer l2 = new StringTokenizer(scan.readLine());
        s = Integer.parseInt(l2.nextToken())-1; t = Integer.parseInt(l2.nextToken())-1;

        StringTokenizer l3 = new StringTokenizer(scan.readLine());
        u = Integer.parseInt(l3.nextToken())-1; v = Integer.parseInt(l3.nextToken())-1;

        adj = new ArrayList<>();
        for (int i = 0;i<num;i++)
            adj.add(new ArrayList<>());

        for (int i = 0;i<m;i++) {
            StringTokenizer st = new StringTokenizer(scan.readLine());
            int a = Integer.parseInt(st.nextToken())-1; int b = Integer.parseInt(st.nextToken())-1; int c = Integer.parseInt(st.nextToken());
            adj.get(a).add(new Pair(b,c)); adj.get(b).add(new Pair(a,c));
        }

        dpU = new long[num]; dpV = new long[num]; Arrays.fill(dpU, Long.MAX_VALUE/2); Arrays.fill(dpV, Long.MAX_VALUE/2);
        udis = dijkstra1(u); vdis = dijkstra1(v);

        ans = udis[v]; dijkstra2();
        System.out.println(ans);
    }

    public static void dijkstra2 () {
        long[] dis = new long[num]; Arrays.fill(dis, Long.MAX_VALUE);
        boolean[] visited = new boolean[num];
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingLong(a->a.val));
        pq.add(new Node(s,0, 0)); dis[s] = 0;

        while (!pq.isEmpty()) {
            Node curr = pq.poll(); int node = curr.n; long d = curr.val; int parent = curr.parent;

            if (!visited[node]) {
                visited[node] = true; dis[node] = d;

                dpU[node] = Math.min(dpU[parent], udis[node]); dpV[node] = Math.min(dpV[parent], vdis[node]);
                for (Pair next : adj.get(node)) {
                    if (next.n!=parent) pq.add(new Node(next.n,d+next.val,node));
                }
            } else if (dis[node]==d) {
                //The if statement is necessary to make sure that the parent node (the one you came before on) used to
                //calculate the dp is actually from the min path you are choosing to purchase (and not some other one)
                if (Math.min(udis[node], dpU[parent]) + Math.min(vdis[node], dpV[parent]) <= dpU[node] + dpV[node]) {
                    dpU[node] = Math.min(udis[node], dpU[parent]);
                    dpV[node] = Math.min(vdis[node], dpV[parent]);
                }
                //No need to add extra vertices since we've already been here with dis = d.
            }
        }

        ans = Math.min(ans, dpU[t]+dpV[t]);
    }

    public static long[] dijkstra1 (int start) {
        long[] dis = new long[num]; Arrays.fill(dis, Long.MAX_VALUE);
        PriorityQueue<Pair> pq = new PriorityQueue<>(Comparator.comparingLong(a->a.val));
        pq.add(new Pair(start,0)); dis[start] = 0;

        while (!pq.isEmpty()) {
            Pair curr = pq.poll(); int node = curr.n; long d = curr.val;
            if (dis[node]!=d) continue;

            for (Pair v : adj.get(node)) {
                int n = v.n; long w = v.val;

                if (d+w<dis[n]) {
                    dis[n] = d+w;
                    pq.add(new Pair(n,dis[n]));
                }
            }
        }

        return dis;
    }


    public static class Pair {
        int n; long val; //node to and value (weight or curr dis)

        Pair (int n, long val) {
            this.n = n; this.val = val;
        }
    }

    public static class Node {
        int n; long val; //node to and value (weight or curr dis)
        int parent; //the node before

        Node (int n, long val, int parent) {
            this.n = n; this.val = val;
            this.parent = parent;
        }
    }

}

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