Submission #1230670

#TimeUsernameProblemLanguageResultExecution timeMemory
1230670uranium235Commuter Pass (JOI18_commuter_pass)Java
31 / 100
1327 ms176200 KiB
//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; else if (dist[val.node] == val.cost) { mins[val.node] = Math.min(mins[val.node], val.min); continue; } dist[val.node] = val.cost; mins[val.node] = Math.min(dists[val.node], val.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; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...