Submission #855871

#	Time	Username	Problem	Language	Result	Execution time	Memory
855871		Oz121	Commuter Pass (JOI18_commuter_pass)	Java	0 / 100	1388 ms	262144 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 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));
        }

        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);
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingLong(a->a.val));

        ArrayList<Integer> temp = new ArrayList<>(); temp.add(s);
        pq.add(new Node(s,0, temp)); dis[s] = 0;

        while (!pq.isEmpty()) {
            Node curr = pq.poll(); int node = curr.n; long d = curr.val; ArrayList<Integer> visited = curr.visited;

            if (dis[node]!=d) continue;

            if (node==t) {
                //System.out.println(visited);
                long m1 = Long.MAX_VALUE; long m2 = Long.MAX_VALUE;
                for (int n : visited) {
                    m1 = Math.min(m1,udis[n]); m2 = Math.min(m2,vdis[n]);
                }

                //System.out.println(m1+" "+m2);

                ans = Math.min(ans,m1+m2);
                continue;
            }

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

                if (d+w<=dis[n]) {
                    dis[n] = d+w;

                    ArrayList<Integer> next = (ArrayList<Integer>) visited.clone(); next.add(n);
                    pq.add(new Node(n,dis[n], next));
                }
            }
        }
    }

    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)
        ArrayList<Integer> visited;

        Node (int n, long val, ArrayList<Integer> visited) {
            this.n = n; this.val = val;
            this.visited = visited;
        }
    }

}

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