結果
問題 | No.848 なかよし旅行 |
ユーザー | kusomushi |
提出日時 | 2019-07-09 04:12:21 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,087 bytes |
コンパイル時間 | 2,748 ms |
コンパイル使用メモリ | 83,660 KB |
実行使用メモリ | 56,100 KB |
最終ジャッジ日時 | 2024-10-07 01:26:43 |
合計ジャッジ時間 | 11,314 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 577 ms
56,100 KB |
testcase_01 | AC | 74 ms
38,340 KB |
testcase_02 | AC | 68 ms
37,572 KB |
testcase_03 | AC | 71 ms
37,684 KB |
testcase_04 | AC | 69 ms
37,676 KB |
testcase_05 | AC | 71 ms
38,036 KB |
testcase_06 | AC | 87 ms
38,696 KB |
testcase_07 | AC | 70 ms
38,216 KB |
testcase_08 | AC | 102 ms
38,612 KB |
testcase_09 | AC | 123 ms
39,628 KB |
testcase_10 | AC | 103 ms
38,732 KB |
testcase_11 | AC | 306 ms
45,720 KB |
testcase_12 | AC | 358 ms
47,300 KB |
testcase_13 | AC | 384 ms
47,280 KB |
testcase_14 | AC | 267 ms
44,024 KB |
testcase_15 | AC | 367 ms
47,724 KB |
testcase_16 | AC | 451 ms
49,484 KB |
testcase_17 | AC | 404 ms
48,388 KB |
testcase_18 | AC | 307 ms
45,832 KB |
testcase_19 | AC | 305 ms
48,384 KB |
testcase_20 | WA | - |
testcase_21 | AC | 424 ms
47,968 KB |
testcase_22 | AC | 384 ms
51,304 KB |
testcase_23 | AC | 179 ms
40,944 KB |
testcase_24 | AC | 66 ms
37,912 KB |
testcase_25 | AC | 495 ms
51,576 KB |
testcase_26 | AC | 68 ms
37,828 KB |
testcase_27 | AC | 68 ms
38,088 KB |
testcase_28 | AC | 67 ms
37,596 KB |
testcase_29 | AC | 66 ms
37,576 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 int solve() { Edge[][] G = adjB(N, E); int[] distR = calcDist(0, G); int[] distP = calcDist(P, G); int[] distQ = calcDist(Q, G); if( distR[P] + distP[Q] + distQ[0] <= T ) { return T; } int ans = -1; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // iで別れてjで待ち合わせる int ri = distR[i]; int ip = distP[i]; int iq = distQ[i]; int pj = distP[j]; int qj = distQ[j]; int 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 int[] calcDist(int root, Edge[][] G) { int[] dist = new int[N]; Arrays.fill(dist, Integer.MAX_VALUE); PriorityQueue<State> q = new PriorityQueue<>(Comparator.comparingInt(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, d; public State(int a, int 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()); } }