Submission #618077
Source Code Expand
import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.InputMismatchException; import java.util.PriorityQueue; public class Main { InputStream is; int __t__ = 1; int __f__ = 0; int __FILE_DEBUG_FLAG__ = __f__; String __DEBUG_FILE_NAME__ = "src/D2"; FastScanner in; PrintWriter out; /* -----------Dijkstra---------- */ public class Edge { int to; int c; int sleepTo; int sleepCost; Edge(int to, int c, int sleepTo, int sleepCost) { this.to = to; this.c = c; this.sleepTo = sleepTo; this.sleepCost = sleepCost; } public String toString() { return "(" + to + "," + c + ")"; } } public class Dijkstra { protected final static int INF = 1_000_000_000; class State implements Comparable<State> { int n; State(int n) { this.n = n; } public int compareTo(State s) { int c1 = res.minCost[n], c2 = res.minCost[s.n]; if (c1 < c2) return -1; else if (c1 > c2) return 1; else return 0; } } DijkstraResult res; Dijkstra() {} /** * This function is for Fixed Graph. * The second Variable "edge" should be fixed graph which is prepared by called method. * @param start root node. * @param edge fixed edges. * @return dijkstra result. */ DijkstraResult doit(int start, int[][] edge) { int n = edge.length; res = new DijkstraResult(n); Arrays.fill(res.minCost, Dijkstra.INF); PriorityQueue<State> pq = new PriorityQueue<State>(); pq.add(new State(start)); res.minCost[start] = 0; res.path[start] = start; while (!pq.isEmpty()) { State s = pq.poll(); for (int i = 0; i < n; i++) { if (res.minCost[i] > res.minCost[s.n] + edge[s.n][i]) { res.minCost[i] = res.minCost[s.n] + edge[s.n][i]; res.path[i] = s.n; pq.add(new State(i)); } } } return res; } /** * return the result of Dijkstra. * This function is for Sparse Graph. * The second Variable "edge" should be sparse graph which is prepared by called method. * @param start root node * @edge sparse graph. * @return dijkstra result */ DijkstraResult doit(int start, ArrayList<Edge>[] edge) { int n = edge.length; res = new DijkstraResult(n); Arrays.fill(res.minCost, Dijkstra.INF); PriorityQueue<State> pq = new PriorityQueue<State>(); pq.add(new State(start)); res.minCost[start] = 0; res.path[start] = start; while (!pq.isEmpty()) { State s = pq.poll(); for (Edge e : edge[s.n]) { if (res.minCost[e.to] > res.minCost[s.n] + e.c) { res.minCost[e.to] = res.minCost[s.n] + e.c; res.path[e.to] = s.n; pq.add(new State(e.to)); } } } return res; } } /** * it contains minCost and path from start node to each nodes. * @author hiro116s * */ class DijkstraResult { int[] minCost; int[] path; DijkstraResult(int n) { minCost = new int[n]; path = new int[n]; } } /*-------------end--------------*/ class P implements Comparable<P> { int n; int cost; P(int n, int cost) { this.n = n; this.cost = cost; } P(int n, int c1, int c2) { this(n, Math.max(c1, c2)); } public int compareTo(P s) { return cost - s.cost; } public String dump(String symbol) { return symbol + " : " + n + " " + cost; } } int MAX = 255000; void solve() { int N = in.nextInt(), M = in.nextInt(), src = in.nextInt(), dst = in.nextInt(); int[] L = new int[M]; int[][] s = new int[M][]; int[][] w = new int[M][]; for (int i = 0; i < M; i++) { L[i] = in.nextInt(); s[i] = new int[L[i]]; w[i] = new int[L[i]-1]; for (int j = 0; j < L[i]; j++) { s[i][j] = in.nextInt(); } for (int j = 0; j < L[i] - 1; j++) { w[i][j] = in.nextInt(); } } ArrayList<Edge>[] g = new ArrayList[N]; for (int i = 0; i < N; i++) { g[i] = new ArrayList<>(); } int[] sum = new int[MAX]; for (int i = 0; i < M; i++) { Arrays.fill(sum, 0); int n = L[i]; for (int j = 1; j < n; j++) { sum[j] = sum[j-1] + w[i][j-1]; } for (int j = 0; j < n - 1; j++) { int from = s[i][j], to = s[i][j+1]; g[to].add(new Edge(from, w[i][j], s[i][n-1], sum[n-1] - sum[j])); g[from].add(new Edge(to, w[i][j], s[i][0], sum[j+1])); } } long res = 0; int[] dmin = new Dijkstra().doit(dst, g).minCost; PriorityQueue<P> pq = new PriorityQueue<>(); pq.add(new P(dst, 0)); int[] minCost = new int[N]; Arrays.fill(minCost, Dijkstra.INF); minCost[dst] = 0; while (!pq.isEmpty()) { P p = pq.poll(); if (minCost[p.n] < p.cost) continue; minCost[p.n] = p.cost; for (Edge e : g[p.n]) { int ncost = Math.max(minCost[p.n] + e.c, dmin[e.sleepTo] + e.sleepCost); pq.add(new P(e.to, ncost)); } } System.out.println(minCost[src]); } public void run() { if (__FILE_DEBUG_FLAG__ == __t__) { try { is = new FileInputStream(__DEBUG_FILE_NAME__); } catch (FileNotFoundException e) { // TODO 自動生成された catch ブロック e.printStackTrace(); } System.out.println("FILE_INPUT!"); } else { is = System.in; } in = new FastScanner(is); out = new PrintWriter(System.out); solve(); } public static void main(String[] args) { new Main().run(); } public void mapDebug(int[][] a) { System.out.println("--------map display---------"); for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { System.out.printf("%3d ", a[i][j]); } System.out.println(); } System.out.println("----------------------------"); System.out.println(); } public void debug(Object... obj) { System.out.println(Arrays.deepToString(obj)); } class FastScanner { private InputStream stream; private byte[] buf = new byte[1024]; private int curChar; private int numChars; public FastScanner(InputStream stream) { this.stream = stream; //stream = new FileInputStream(new File("dec.in")); } int read() { if (numChars == -1) throw new InputMismatchException(); if (curChar >= numChars) { curChar = 0; try { numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) return -1; } return buf[curChar++]; } boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } boolean isEndline(int c) { return c == '\n' || c == '\r' || c == -1; } int nextInt() { return Integer.parseInt(next()); } int[] nextIntArray(int n) { int[] array = new int[n]; for (int i = 0; i < n; i++) array[i] = nextInt(); return array; } int[][] nextIntMap(int n, int m) { int[][] map = new int[n][m]; for (int i = 0; i < n; i++) { map[i] = in.nextIntArray(m); } return map; } long nextLong() { return Long.parseLong(next()); } long[] nextLongArray(int n) { long[] array = new long[n]; for (int i = 0; i < n; i++) array[i] = nextLong(); return array; } long[][] nextLongMap(int n, int m) { long[][] map = new long[n][m]; for (int i = 0; i < n; i++) { map[i] = in.nextLongArray(m); } return map; } double nextDouble() { return Double.parseDouble(next()); } double[] nextDoubleArray(int n) { double[] array = new double[n]; for (int i = 0; i < n; i++) array[i] = nextDouble(); return array; } double[][] nextDoubleMap(int n, int m) { double[][] map = new double[n][m]; for (int i = 0; i < n; i++) { map[i] = in.nextDoubleArray(m); } return map; } String next() { int c = read(); while (isSpaceChar(c)) c = read(); StringBuilder res = new StringBuilder(); do { res.appendCodePoint(c); c = read(); } while (!isSpaceChar(c)); return res.toString(); } String[] nextStringArray(int n) { String[] array = new String[n]; for (int i = 0; i < n; i++) array[i] = next(); return array; } String nextLine() { int c = read(); while (isEndline(c)) c = read(); StringBuilder res = new StringBuilder(); do { res.appendCodePoint(c); c = read(); } while (!isEndline(c)); return res.toString(); } } }
Submission Info
Submission Time | |
---|---|
Task | C - メンテナンス明け |
User | hiro116s |
Language | Java (OpenJDK 1.7.0) |
Score | 100 |
Code Size | 8780 Byte |
Status | AC |
Exec Time | 988 ms |
Memory | 43644 KB |
Compile Error
Note: ./Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
Judge Result
Set Name | Subtask1 | Subtask2 | ||||
---|---|---|---|---|---|---|
Score / Max Score | 50 / 50 | 50 / 50 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Subtask1 | small/00_sample00, small/00_sample01, small/00_sample02, small/10_small-0000, small/10_small-0001, small/10_small-0002, small/10_small-0003, small/10_small-0004, small/10_small-0005, small/10_small-0006, small/10_small-0007, small/10_small-0008, small/10_small-0009, small/10_small-0010, small/10_small-0011, small/10_small-0012, small/10_small-0013, small/10_small-0014, small/10_small-0015, small/10_small-0016, small/10_small-0017, small/10_small-0018, small/10_small-0019, small/30_max_small, small/40_simple_0000, small/40_simple_0001, small/40_simple_0002, small/40_simple_0003, small/40_simple_0004, small/40_simple_0005, small/40_simple_0006, small/40_simple_0007, small/40_simple_0008, small/40_simple_0009, small/40_simple_0010, small/40_simple_0011, small/40_simple_0012, small/40_simple_0013, small/40_simple_0014, small/40_simple_0015, small/40_simple_0016, small/40_simple_0017, small/40_simple_0018, small/40_simple_0019, small/90_dijkstra_killer_00, small/90_dijkstra_killer_01, small/91_tayama_killer_00, small/91_tayama_killer_01, small/91_tayama_killer_02, small/91_tayama_killer_03, small/91_tayama_killer_04, small/91_tayama_killer_05 |
Subtask2 | large/20_large-00, large/20_large-01, large/20_large-02, large/20_large-03, large/20_large-04, large/31_max_large |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
large/20_large-00 | AC | 955 ms | 43644 KB |
large/20_large-01 | AC | 988 ms | 42068 KB |
large/20_large-02 | AC | 962 ms | 41928 KB |
large/20_large-03 | AC | 977 ms | 42268 KB |
large/20_large-04 | AC | 936 ms | 42052 KB |
large/31_max_large | AC | 715 ms | 40500 KB |
small/00_sample00 | AC | 373 ms | 24532 KB |
small/00_sample01 | AC | 359 ms | 24520 KB |
small/00_sample02 | AC | 371 ms | 24516 KB |
small/10_small-0000 | AC | 436 ms | 24788 KB |
small/10_small-0001 | AC | 383 ms | 24796 KB |
small/10_small-0002 | AC | 379 ms | 24692 KB |
small/10_small-0003 | AC | 377 ms | 24700 KB |
small/10_small-0004 | AC | 397 ms | 24800 KB |
small/10_small-0005 | AC | 373 ms | 24768 KB |
small/10_small-0006 | AC | 415 ms | 24868 KB |
small/10_small-0007 | AC | 375 ms | 24760 KB |
small/10_small-0008 | AC | 379 ms | 24808 KB |
small/10_small-0009 | AC | 379 ms | 24876 KB |
small/10_small-0010 | AC | 374 ms | 24704 KB |
small/10_small-0011 | AC | 385 ms | 24800 KB |
small/10_small-0012 | AC | 394 ms | 24788 KB |
small/10_small-0013 | AC | 416 ms | 24884 KB |
small/10_small-0014 | AC | 382 ms | 24764 KB |
small/10_small-0015 | AC | 396 ms | 24732 KB |
small/10_small-0016 | AC | 390 ms | 24788 KB |
small/10_small-0017 | AC | 395 ms | 24764 KB |
small/10_small-0018 | AC | 444 ms | 24752 KB |
small/10_small-0019 | AC | 406 ms | 24728 KB |
small/30_max_small | AC | 360 ms | 24656 KB |
small/40_simple_0000 | AC | 365 ms | 24248 KB |
small/40_simple_0001 | AC | 379 ms | 24416 KB |
small/40_simple_0002 | AC | 357 ms | 24448 KB |
small/40_simple_0003 | AC | 371 ms | 24468 KB |
small/40_simple_0004 | AC | 369 ms | 24452 KB |
small/40_simple_0005 | AC | 367 ms | 24316 KB |
small/40_simple_0006 | AC | 371 ms | 24320 KB |
small/40_simple_0007 | AC | 354 ms | 24520 KB |
small/40_simple_0008 | AC | 354 ms | 24468 KB |
small/40_simple_0009 | AC | 362 ms | 24484 KB |
small/40_simple_0010 | AC | 355 ms | 24452 KB |
small/40_simple_0011 | AC | 360 ms | 24508 KB |
small/40_simple_0012 | AC | 357 ms | 24328 KB |
small/40_simple_0013 | AC | 397 ms | 24352 KB |
small/40_simple_0014 | AC | 473 ms | 24284 KB |
small/40_simple_0015 | AC | 363 ms | 24416 KB |
small/40_simple_0016 | AC | 355 ms | 24424 KB |
small/40_simple_0017 | AC | 362 ms | 24480 KB |
small/40_simple_0018 | AC | 365 ms | 24332 KB |
small/40_simple_0019 | AC | 361 ms | 24336 KB |
small/90_dijkstra_killer_00 | AC | 381 ms | 24496 KB |
small/90_dijkstra_killer_01 | AC | 408 ms | 24516 KB |
small/91_tayama_killer_00 | AC | 352 ms | 24528 KB |
small/91_tayama_killer_01 | AC | 378 ms | 24484 KB |
small/91_tayama_killer_02 | AC | 360 ms | 24328 KB |
small/91_tayama_killer_03 | AC | 386 ms | 24532 KB |
small/91_tayama_killer_04 | AC | 385 ms | 24264 KB |
small/91_tayama_killer_05 | AC | 421 ms | 24424 KB |