結果
問題 | No.848 なかよし旅行 |
ユーザー | kusomushi |
提出日時 | 2019-07-09 03:47:56 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,802 bytes |
コンパイル時間 | 2,427 ms |
コンパイル使用メモリ | 83,904 KB |
実行使用メモリ | 57,172 KB |
最終ジャッジ日時 | 2024-10-07 01:25:20 |
合計ジャッジ時間 | 9,269 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 539 ms
57,172 KB |
testcase_01 | AC | 72 ms
38,080 KB |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | AC | 61 ms
37,500 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | AC | 63 ms
37,888 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | AC | 289 ms
46,636 KB |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | AC | 56 ms
37,188 KB |
testcase_25 | WA | - |
testcase_26 | AC | 58 ms
37,200 KB |
testcase_27 | AC | 56 ms
37,520 KB |
testcase_28 | AC | 56 ms
37,604 KB |
testcase_29 | AC | 56 ms
37,604 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); int ans = -1; for (int i = 0; i < N; i++) { int r = distR[i]; int p = distP[i]; int q = distQ[i]; if( r*2 + p*2 + q*2 <= T ) { return T; } else if( r*2 + p*2 > T || r*2 + q*2 > T ) { continue; // 間に合わない } else { // 別行動してる時間だけ引く ans = Math.max(ans, T - Math.max(p, q) * 2); } } 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()); } }