제출 #1230671

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1230671		uranium235	Commuter Pass (JOI18_commuter_pass)	Java	100 / 100	1429 ms	177472 KiB

commuter_pass

//package ojuz;

import java.io.*;
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.IntFunction;

public class commuter_pass {
    public static final PriorityQueue<Token> pq = new PriorityQueue<>(Comparator.comparingLong((Token i) -> i.cost).thenComparingInt(i -> i.node));
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] first = reader.readLine().split(" ");
        int n = Integer.parseInt(first[0]), m = Integer.parseInt(first[1]);
        first = reader.readLine().split(" ");
        int s = Integer.parseInt(first[0]) - 1, t = Integer.parseInt(first[1]) - 1;
        first = reader.readLine().split(" ");
        int u = Integer.parseInt(first[0]) - 1, v = Integer.parseInt(first[1]) - 1;
        Graph g = new Graph(n, 2 * m);
        for (int i = 0; i < m; i++) {
            String[] edge = reader.readLine().split(" ");
            int a = Integer.parseInt(edge[0]) - 1, b = Integer.parseInt(edge[1]) - 1, w = Integer.parseInt(edge[2]);
            g.add(a, b, w);
            g.add(b, a, w);
        }
        IntFunction<long[]> find = start -> {
            pq.clear();
            pq.add(new Token(start, 0, -1));
            long[] dist = new long[n];
            Arrays.fill(dist, Long.MAX_VALUE / 2);
            while (!pq.isEmpty()) {
                Token val = pq.poll();
                if (dist[val.node] <= val.cost) continue;
                dist[val.node] = val.cost;
                for (int i = g.head[val.node]; i != -1; i = g.edges[i][1]) {
                    pq.add(new Token(g.edges[i][0], g.edges[i][2] + val.cost, -1));
                }
            }
            return dist;
        };
        long[] distU = find.apply(u);
        long[] distV = find.apply(v);
        BiFunction<Integer, long[], long[][]> findMin = (start, dists) -> {
            pq.clear();
            pq.add(new Token(start, 0, dists[start]));
            long[] dist = new long[n];
            long[] mins = new long[n];
            Arrays.fill(dist, Long.MAX_VALUE / 2);
            Arrays.fill(mins, Long.MAX_VALUE / 2);
            while (!pq.isEmpty()) {
                Token val = pq.poll();
                if (dist[val.node] < val.cost) continue;
                if (dist[val.node] == val.cost) throw new RuntimeException();
                dist[val.node] = val.cost;
                mins[val.node] = Math.min(dists[val.node], val.min);
                while (!pq.isEmpty() && pq.peek().node == val.node && pq.peek().cost == val.cost) mins[val.node] = Math.min(mins[val.node], pq.poll().min);
                for (int i = g.head[val.node]; i != -1; i = g.edges[i][1]   ) {
                    pq.add(new Token(g.edges[i][0], g.edges[i][2] + val.cost, mins[val.node]));
                }
            }
            return new long[][] { dist, mins };
        };
        long[][] distS = findMin.apply(s, distU);
        long[][] distT = findMin.apply(t, distU);
        long ans = Long.MAX_VALUE;
        long distST = distS[0][t];
        if (distST != distT[0][s]) throw new RuntimeException();
        for (int i = 0; i < n; i++) {
            if (distST == distS[0][i] + distT[0][i]) {
                ans = Math.min(ans, distS[1][i] + distV[i]);
                ans = Math.min(ans, distT[1][i] + distV[i]);
            }
        }
        System.out.println(Math.min(ans, distU[v]));
    }

    static class Graph {
        public final int[][] edges;
        public final int[] head;
        public int ptr;
        public Graph(int n, int m) {
            this.edges = new int[m][3];
            this.head = new int[n];
            Arrays.fill(head, -1);
        }

        public void add(int a, int b, int w) {
            edges[ptr][0] = b;
            edges[ptr][1] = head[a];
            edges[ptr][2] = w;
            head[a] = ptr++;
        }
    }

    static class Token {
        public final int node;
        public final long cost, min;
        public Token(int n, long w, long m) {
            this.node = n;
            this.cost = w;
            this.min = m;
        }
    }
}

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