제출 #857387

#제출 시각아이디문제언어결과실행 시간메모리
857387Oz121Commuter Pass (JOI18_commuter_pass)Java
31 / 100
977 ms73372 KiB
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 { //FileReader file = new FileReader("/Users/owenzhou/Downloads/2018-ho-t4/in/01-02.txt"); 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) { dpU[node] = Math.min(dpU[node], dpU[parent]); dpV[node] = Math.min(dpV[node], dpV[parent]); /*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; Node (int n, long val, int parent) { this.n = n; this.val = val; this.parent = parent; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...