Submission #1989021
Source Code Expand
import java.util.HashMap; import java.util.Map; import java.util.TreeSet; public class Main { private static void solve() { int n = ni(); int m = ni(); int[] from = new int[m]; int[] to = new int[m]; int[] w = new int[m]; for (int i = 0; i < m; i++) { from[i] = ni() - 1; to[i] = ni() - 1; w[i] = ni(); } int[][][] g = packWU(n, from, to, w); long ret = dijk(g); System.out.println(ret); } public static long dijk(int[][][] g) { Map<Long, Long> td = new HashMap<>(); long inf = 10000000; //[v, color, len] TreeSet<long[]> q = new TreeSet<>((a, b) -> { long ha = a[1] * inf + a[0]; long hb = b[1] * inf + b[0]; if (td.containsKey(ha) && td.containsKey(hb) && td.get(ha) - td.get(hb) != 0) return Long.compare(td.get(ha), td.get(hb)); if (a[1] - b[1] != 0) return Long.compare(a[1], b[1]); return Long.compare(a[0], b[0]); }); int target = g.length - 1; long[] start = new long[] {0, 0}; q.add(start); td.put(0L, 0L); long ret = -1; while (q.size() > 0) { long[] v = q.pollFirst(); int cur = (int)v[0]; int color = (int)v[1]; long d = td.get(color * inf + cur); for (int i = 0; i < g[cur].length; i++) { int nv = g[cur][i][0]; int nc = g[cur][i][1]; long[] next = new long[] {nv, nc}; long nd = d; if (color == 0) { nd ++; } else if (color == nc) { } else { continue; } long nextHash = next[1] * inf + next[0]; if (!td.containsKey(nextHash) || nd < td.get(nextHash)) { q.remove(next); td.put(nextHash, nd); q.add(next); if (next[0] == target) { ret = ret < 0 ? nd : Math.min(ret, nd); } } } long hash = cur; if (!td.containsKey(hash) || d < td.get(hash)) { long[] next = new long[] {cur, 0}; q.remove(next); td.put(hash, d); q.add(next); } } return ret; } public static int[][][] packWU(int n, int[] from, int[] to, int[] w) { return packWU(n, from, to, w, from.length); } public static int[][][] packWU(int n, int[] from, int[] to, int[] w, int sup) { int[][][] g = new int[n][][]; int[] p = new int[n]; for (int i = 0; i < sup; i++) p[from[i]]++; for (int i = 0; i < sup; i++) p[to[i]]++; for (int i = 0; i < n; i++) g[i] = new int[p[i]][2]; for (int i = 0; i < sup; i++) { --p[from[i]]; g[from[i]][p[from[i]]][0] = to[i]; g[from[i]][p[from[i]]][1] = w[i]; --p[to[i]]; g[to[i]][p[to[i]]][0] = from[i]; g[to[i]][p[to[i]]][1] = w[i]; } return g; } public static void main(String[] args) { new Thread(null, new Runnable() { @Override public void run() { long start = System.currentTimeMillis(); String debug = System.getProperty("debug"); if (debug != null) { try { is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug)); } catch (Exception e) { throw new RuntimeException(e); } } reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768); solve(); out.flush(); tr((System.currentTimeMillis() - start) + "ms"); } }, "", 64000000).start(); } private static java.io.InputStream is = System.in; private static java.io.PrintWriter out = new java.io.PrintWriter(System.out); private static java.util.StringTokenizer tokenizer = null; private static java.io.BufferedReader reader; public static String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new java.util.StringTokenizer(reader.readLine()); } catch (Exception e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } private static double nd() { return Double.parseDouble(next()); } private static long nl() { return Long.parseLong(next()); } private static int[] na(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = ni(); return a; } private static char[] ns() { return next().toCharArray(); } private static long[] nal(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nl(); return a; } private static int[][] ntable(int n, int m) { int[][] table = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { table[i][j] = ni(); } } return table; } private static int[][] nlist(int n, int m) { int[][] table = new int[m][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { table[j][i] = ni(); } } return table; } private static int ni() { return Integer.parseInt(next()); } private static void tr(Object... o) { if (is != System.in) System.out.println(java.util.Arrays.deepToString(o)); } }
Submission Info
Submission Time | |
---|---|
Task | E - Snuke's Subway Trip |
User | hiromi_ayase |
Language | Java8 (OpenJDK 1.8.0) |
Score | 0 |
Code Size | 5327 Byte |
Status | TLE |
Exec Time | 3164 ms |
Memory | 404552 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 600 | ||||||
Status | AC |
|
Set Name | Test Cases |
---|---|
Sample | |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, sample_01.txt, sample_02.txt, sample_03.txt, w1.txt, w10.txt, w11.txt, w12.txt, w13.txt, w14.txt, w15.txt, w16.txt, w17.txt, w18.txt, w2.txt, w3.txt, w4.txt, w5.txt, w6.txt, w7.txt, w8.txt, w9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | AC | 212 ms | 27348 KB |
02.txt | MLE | 1921 ms | 356268 KB |
03.txt | TLE | 3072 ms | 398616 KB |
04.txt | AC | 401 ms | 60492 KB |
05.txt | MLE | 2051 ms | 361064 KB |
06.txt | AC | 736 ms | 105948 KB |
07.txt | AC | 1286 ms | 194384 KB |
08.txt | MLE | 2804 ms | 386308 KB |
09.txt | AC | 1280 ms | 191116 KB |
10.txt | AC | 1254 ms | 194536 KB |
11.txt | MLE | 1703 ms | 342592 KB |
12.txt | AC | 560 ms | 86860 KB |
13.txt | AC | 1470 ms | 181672 KB |
14.txt | MLE | 1606 ms | 327656 KB |
15.txt | AC | 978 ms | 189260 KB |
16.txt | MLE | 1639 ms | 321384 KB |
17.txt | MLE | 1905 ms | 341652 KB |
18.txt | AC | 804 ms | 119784 KB |
19.txt | AC | 1394 ms | 223648 KB |
20.txt | MLE | 2331 ms | 371672 KB |
21.txt | TLE | 3164 ms | 392412 KB |
22.txt | MLE | 2623 ms | 382104 KB |
23.txt | MLE | 2166 ms | 356948 KB |
24.txt | MLE | 1853 ms | 329872 KB |
25.txt | AC | 834 ms | 107072 KB |
26.txt | AC | 1602 ms | 207040 KB |
27.txt | MLE | 1822 ms | 353668 KB |
28.txt | MLE | 2114 ms | 347152 KB |
29.txt | MLE | 1771 ms | 336728 KB |
30.txt | MLE | 1879 ms | 334972 KB |
31.txt | MLE | 1808 ms | 274484 KB |
32.txt | AC | 1160 ms | 201920 KB |
33.txt | MLE | 1808 ms | 327324 KB |
34.txt | MLE | 1692 ms | 358364 KB |
35.txt | AC | 554 ms | 72532 KB |
36.txt | AC | 856 ms | 151480 KB |
37.txt | MLE | 1721 ms | 366960 KB |
38.txt | MLE | 2149 ms | 371576 KB |
sample_01.txt | AC | 159 ms | 26196 KB |
sample_02.txt | AC | 150 ms | 24532 KB |
sample_03.txt | AC | 155 ms | 26324 KB |
w1.txt | MLE | 1814 ms | 309760 KB |
w10.txt | AC | 1106 ms | 132392 KB |
w11.txt | MLE | 1083 ms | 344488 KB |
w12.txt | MLE | 1501 ms | 367004 KB |
w13.txt | MLE | 1356 ms | 366016 KB |
w14.txt | AC | 1393 ms | 218612 KB |
w15.txt | AC | 678 ms | 102452 KB |
w16.txt | AC | 594 ms | 98912 KB |
w17.txt | AC | 666 ms | 107788 KB |
w18.txt | AC | 1015 ms | 118356 KB |
w2.txt | MLE | 1347 ms | 278772 KB |
w3.txt | MLE | 2523 ms | 349056 KB |
w4.txt | AC | 1065 ms | 200984 KB |
w5.txt | TLE | 3163 ms | 391016 KB |
w6.txt | MLE | 2606 ms | 370268 KB |
w7.txt | TLE | 3158 ms | 371564 KB |
w8.txt | TLE | 3160 ms | 389216 KB |
w9.txt | MLE | 2486 ms | 404552 KB |