Submission #1989112
Source Code Expand
import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.PriorityQueue; import java.util.Queue; import java.util.Set; public class Main { static int currentId = 0; static int[][][] g; static List<int[]> edge = new ArrayList<>(); static Map<Long, Integer> c2id = new HashMap<>(); static Set<Integer> visited = new HashSet<>();; 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(); } g = packWU(n, from, to, w); dfs(0, 0); int target = id(n - 1, 0); int l = edge.size(); int[] nf = new int[l]; int[] nt = new int[l]; int[] nw = new int[l]; for (int i = 0; i < l; i ++) { int[] v = edge.get(i); nf[i] = v[0]; nt[i] = v[1]; nw[i] = v[2]; } int[][][] h = packWU(c2id.size(), nf, nt, nw); int[] d = dijk(h, 0); System.out.println(d[target] >= Integer.MAX_VALUE / 2 ? -1 : d[target]); } public static int[] dijk(int[][][] g, int from) { int n = g.length; int[] d = new int[n]; Arrays.fill(d, Integer.MAX_VALUE); Queue<int[]> q = new PriorityQueue<int[]>(100000, new Comparator<int[]>(){ public int compare(int[] a, int[] b) { if(a[1] - b[1] != 0)return a[1] - b[1]; return a[0] - b[0]; } }); q.add(new int[]{from, 0}); d[from] = 0; while(q.size() > 0){ int[] cur = q.poll(); for(int[] e : g[cur[0]]){ int next = e[0]; int nd = d[cur[0]] + e[1]; if(nd < d[next]){ d[next] = nd; q.add(new int[]{next, nd}); } } } return d; } private static void dfs(int now, int company) { visited.add(id(now, company)); for (int[] next : g[now]) { int nc = next[1]; int nv = next[0]; if (visited.contains(id(nv, nc))) continue; if (company == 0) { edge.add(new int[] {id(now, 0), id(nv, nc), 1}); dfs(nv, nc); } else if (nc == company) { edge.add(new int[] {id(now, company), id(nv, nc), 0}); dfs(nv, nc); } } if (!visited.contains(id(now, 0))) { edge.add(new int[] {id(now, company), id(now, 0), 0}); dfs(now, 0); } } private static int id(int node, int company) { long hash = company * 10000000L + node; if (c2id.containsKey(hash)) { return c2id.get(hash); } else { int id = currentId; c2id.put(hash, id); currentId++; return id; } } public static int[][][] packWU(int n, int[] from, int[] to, int[] w) { int sup = from.length; 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 | 6016 Byte |
Status | WA |
Exec Time | 3163 ms |
Memory | 405060 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 | WA | 92 ms | 24020 KB |
02.txt | TLE | 3159 ms | 375120 KB |
03.txt | MLE | 1961 ms | 315088 KB |
04.txt | AC | 339 ms | 62316 KB |
05.txt | MLE | 1689 ms | 256344 KB |
06.txt | AC | 1608 ms | 239776 KB |
07.txt | WA | 1551 ms | 203480 KB |
08.txt | MLE | 2471 ms | 318192 KB |
09.txt | WA | 1881 ms | 224832 KB |
10.txt | MLE | 1802 ms | 257992 KB |
11.txt | WA | 1303 ms | 164644 KB |
12.txt | WA | 478 ms | 74024 KB |
13.txt | WA | 1273 ms | 147708 KB |
14.txt | WA | 1578 ms | 174548 KB |
15.txt | AC | 1416 ms | 155356 KB |
16.txt | WA | 1506 ms | 176624 KB |
17.txt | WA | 1651 ms | 236432 KB |
18.txt | WA | 752 ms | 108648 KB |
19.txt | WA | 1597 ms | 181744 KB |
20.txt | WA | 1459 ms | 209292 KB |
21.txt | TLE | 3158 ms | 231400 KB |
22.txt | TLE | 3163 ms | 335076 KB |
23.txt | MLE | 2377 ms | 278268 KB |
24.txt | WA | 1721 ms | 178392 KB |
25.txt | WA | 609 ms | 104100 KB |
26.txt | WA | 780 ms | 121772 KB |
27.txt | WA | 1293 ms | 179268 KB |
28.txt | WA | 1232 ms | 161764 KB |
29.txt | WA | 1287 ms | 173792 KB |
30.txt | WA | 1468 ms | 172420 KB |
31.txt | WA | 1205 ms | 174524 KB |
32.txt | AC | 1228 ms | 165732 KB |
33.txt | WA | 1593 ms | 180900 KB |
34.txt | MLE | 2396 ms | 384088 KB |
35.txt | AC | 586 ms | 83840 KB |
36.txt | WA | 850 ms | 178544 KB |
37.txt | MLE | 2903 ms | 395868 KB |
38.txt | MLE | 2956 ms | 396152 KB |
sample_01.txt | AC | 74 ms | 23252 KB |
sample_02.txt | AC | 76 ms | 21332 KB |
sample_03.txt | AC | 73 ms | 23508 KB |
w1.txt | WA | 1614 ms | 168024 KB |
w10.txt | AC | 873 ms | 136028 KB |
w11.txt | MLE | 1813 ms | 345068 KB |
w12.txt | MLE | 2212 ms | 352000 KB |
w13.txt | MLE | 2587 ms | 382404 KB |
w14.txt | AC | 1387 ms | 237284 KB |
w15.txt | AC | 427 ms | 99152 KB |
w16.txt | AC | 835 ms | 118408 KB |
w17.txt | AC | 779 ms | 122868 KB |
w18.txt | WA | 791 ms | 146284 KB |
w2.txt | WA | 1592 ms | 170460 KB |
w3.txt | MLE | 1876 ms | 260712 KB |
w4.txt | AC | 1157 ms | 178876 KB |
w5.txt | TLE | 3162 ms | 347236 KB |
w6.txt | MLE | 1763 ms | 274552 KB |
w7.txt | TLE | 3158 ms | 233876 KB |
w8.txt | TLE | 3159 ms | 313444 KB |
w9.txt | TLE | 3163 ms | 405060 KB |