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
AC × 14
WA × 25
TLE × 7
MLE × 13
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