結果
問題 | No.848 なかよし旅行 |
ユーザー | kusomushi |
提出日時 | 2019-07-09 04:15:31 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 631 ms / 2,000 ms |
コード長 | 6,113 bytes |
コンパイル時間 | 2,884 ms |
コンパイル使用メモリ | 83,968 KB |
実行使用メモリ | 55,144 KB |
最終ジャッジ日時 | 2024-11-08 00:59:42 |
合計ジャッジ時間 | 11,891 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 631 ms
55,144 KB |
testcase_01 | AC | 78 ms
38,056 KB |
testcase_02 | AC | 71 ms
38,044 KB |
testcase_03 | AC | 72 ms
37,804 KB |
testcase_04 | AC | 75 ms
37,900 KB |
testcase_05 | AC | 70 ms
38,124 KB |
testcase_06 | AC | 90 ms
38,624 KB |
testcase_07 | AC | 76 ms
38,320 KB |
testcase_08 | AC | 110 ms
38,592 KB |
testcase_09 | AC | 133 ms
39,928 KB |
testcase_10 | AC | 106 ms
38,900 KB |
testcase_11 | AC | 319 ms
46,752 KB |
testcase_12 | AC | 365 ms
49,940 KB |
testcase_13 | AC | 408 ms
47,212 KB |
testcase_14 | AC | 278 ms
44,120 KB |
testcase_15 | AC | 396 ms
47,832 KB |
testcase_16 | AC | 472 ms
50,000 KB |
testcase_17 | AC | 430 ms
50,920 KB |
testcase_18 | AC | 325 ms
48,764 KB |
testcase_19 | AC | 300 ms
45,104 KB |
testcase_20 | AC | 202 ms
41,288 KB |
testcase_21 | AC | 432 ms
49,512 KB |
testcase_22 | AC | 413 ms
48,516 KB |
testcase_23 | AC | 196 ms
40,952 KB |
testcase_24 | AC | 71 ms
37,924 KB |
testcase_25 | AC | 540 ms
49,740 KB |
testcase_26 | AC | 71 ms
37,696 KB |
testcase_27 | AC | 71 ms
37,936 KB |
testcase_28 | AC | 71 ms
37,816 KB |
testcase_29 | AC | 73 ms
38,108 KB |
ソースコード
import java.io.*; import java.util.*; import java.util.function.Function; public class Main { static int N, M, P, Q, T; static Edge[] E; public static void main(String[] args) { FastScanner sc = new FastScanner(System.in); N = sc.nextInt(); M = sc.nextInt(); P = sc.nextInt()-1; Q = sc.nextInt()-1; T = sc.nextInt(); E = new Edge[M]; for (int i = 0; i < M; i++) { E[i] = new Edge(sc.nextInt()-1, sc.nextInt()-1, sc.nextInt()); } System.out.println(solve()); } static long solve() { Edge[][] G = adjB(N, E); long[] distR = calcDist(0, G); long[] distP = calcDist(P, G); long[] distQ = calcDist(Q, G); if( distR[P] + distP[Q] + distQ[0] <= T ) { return T; } long ans = -1; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // iで別れてjで待ち合わせる long ri = distR[i]; long ip = distP[i]; long iq = distQ[i]; long pj = distP[j]; long qj = distQ[j]; long jr = distR[j]; if( ri + ip + pj + jr > T || ri + iq + qj + jr > T ) { continue; // 間に合わない } else { // 別行動してる時間だけ引く ans = Math.max(ans, T - Math.max(ip+pj, iq+qj)); } } } return ans; } static long[] calcDist(int root, Edge[][] G) { long[] dist = new long[N]; Arrays.fill(dist, Long.MAX_VALUE); PriorityQueue<State> q = new PriorityQueue<>(Comparator.comparingLong(s -> s.d)); q.add(new State(root, 0)); dist[root] = 0; while( !q.isEmpty() ) { State s = q.poll(); if( dist[s.a] != s.d ) continue; for (Edge e : G[s.a]) { int b = e.a == s.a ? e.b : e.a; if( dist[b] > dist[s.a] + e.c ) { dist[b] = dist[s.a] + e.c; q.add( new State(b, dist[b]) ); } } } return dist; } static class State { int a; long d; public State(int a, long d) { this.a = a; this.d = d; } } static Edge[][] adjB(int n, Edge[] E) { Edge[][] adj = new Edge[n][]; int[] cnt = new int[n]; for (Edge e : E) { cnt[e.a]++; cnt[e.b]++; } for (int i = 0; i < n; i++) { adj[i] = new Edge[cnt[i]]; } for (Edge e : E) { adj[e.a][--cnt[e.a]] = e; adj[e.b][--cnt[e.b]] = e; } return adj; } static class Edge { int a, b, c; public Edge(int a, int b, int c) { this.a = a; this.b = b; this.c = c; } } @SuppressWarnings("unused") static class FastScanner { private BufferedReader reader; private StringTokenizer tokenizer; FastScanner(InputStream in) { reader = new BufferedReader(new InputStreamReader(in)); tokenizer = null; } String next() { if (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } String nextLine() { if (tokenizer == null || !tokenizer.hasMoreTokens()) { try { return reader.readLine(); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken("\n"); } long nextLong() { return Long.parseLong(next()); } int nextInt() { return Integer.parseInt(next()); } int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } int[] nextIntArray(int n, int delta) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt() + delta; return a; } long[] nextLongArray(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nextLong(); return a; } } static <A> void writeLines(A[] as, Function<A, String> f) { PrintWriter pw = new PrintWriter(System.out); for (A a : as) { pw.println(f.apply(a)); } pw.flush(); } static void writeLines(int[] as) { PrintWriter pw = new PrintWriter(System.out); for (int a : as) pw.println(a); pw.flush(); } static void writeLines(long[] as) { PrintWriter pw = new PrintWriter(System.out); for (long a : as) pw.println(a); pw.flush(); } static int max(int... as) { int max = Integer.MIN_VALUE; for (int a : as) max = Math.max(a, max); return max; } static int min(int... as) { int min = Integer.MAX_VALUE; for (int a : as) min = Math.min(a, min); return min; } static void debug(Object... args) { StringJoiner j = new StringJoiner(" "); for (Object arg : args) { if (arg instanceof int[]) j.add(Arrays.toString((int[]) arg)); else if (arg instanceof long[]) j.add(Arrays.toString((long[]) arg)); else if (arg instanceof double[]) j.add(Arrays.toString((double[]) arg)); else if (arg instanceof Object[]) j.add(Arrays.toString((Object[]) arg)); else j.add(arg.toString()); } System.err.println(j.toString()); } }