結果
問題 | No.1607 Kth Maximum Card |
ユーザー | cyclerecycle9 |
提出日時 | 2021-09-02 14:25:33 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 2,815 ms / 3,500 ms |
コード長 | 5,532 bytes |
コンパイル時間 | 4,100 ms |
コンパイル使用メモリ | 77,236 KB |
実行使用メモリ | 109,020 KB |
最終ジャッジ日時 | 2023-08-20 00:43:54 |
合計ジャッジ時間 | 40,686 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 44 ms
49,492 KB |
testcase_01 | AC | 43 ms
49,488 KB |
testcase_02 | AC | 44 ms
49,468 KB |
testcase_03 | AC | 44 ms
49,660 KB |
testcase_04 | AC | 44 ms
49,604 KB |
testcase_05 | AC | 44 ms
49,380 KB |
testcase_06 | AC | 44 ms
49,320 KB |
testcase_07 | AC | 43 ms
49,352 KB |
testcase_08 | AC | 2,530 ms
109,020 KB |
testcase_09 | AC | 2,367 ms
89,252 KB |
testcase_10 | AC | 2,815 ms
97,944 KB |
testcase_11 | AC | 661 ms
66,564 KB |
testcase_12 | AC | 2,228 ms
83,436 KB |
testcase_13 | AC | 466 ms
49,252 KB |
testcase_14 | AC | 534 ms
50,924 KB |
testcase_15 | AC | 1,675 ms
80,064 KB |
testcase_16 | AC | 479 ms
48,912 KB |
testcase_17 | AC | 207 ms
43,924 KB |
testcase_18 | AC | 1,092 ms
65,680 KB |
testcase_19 | AC | 770 ms
71,700 KB |
testcase_20 | AC | 869 ms
61,672 KB |
testcase_21 | AC | 939 ms
62,616 KB |
testcase_22 | AC | 1,789 ms
91,876 KB |
testcase_23 | AC | 1,768 ms
91,508 KB |
testcase_24 | AC | 810 ms
59,000 KB |
testcase_25 | AC | 548 ms
52,504 KB |
testcase_26 | AC | 686 ms
55,428 KB |
testcase_27 | AC | 795 ms
59,480 KB |
testcase_28 | AC | 751 ms
68,988 KB |
testcase_29 | AC | 1,502 ms
75,972 KB |
testcase_30 | AC | 2,324 ms
89,636 KB |
testcase_31 | AC | 1,345 ms
67,100 KB |
testcase_32 | AC | 931 ms
80,544 KB |
testcase_33 | AC | 916 ms
80,488 KB |
testcase_34 | AC | 889 ms
80,764 KB |
testcase_35 | AC | 919 ms
82,740 KB |
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.math.BigDecimal; import java.math.RoundingMode; import java.util.*; public class Main { static final long MOD=1000000007; static final long MOD1=998244353; static int ans=0; public static void main(String[] args){ PrintWriter out = new PrintWriter(System.out); InputReader sc=new InputReader(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int K = sc.nextInt(); graph G = new graph(N); for (int i = 0; i < M; i++) { int a = sc.nextInt()-1; int b = sc.nextInt()-1; long w = sc.nextLong(); G.addEdge(a, b, w); G.addEdge(b, a, w); } long from=0; long to=2*100001; while ((to-from)>=1) { long mid=(to-from)/2+from; if (f(mid, G, N, K)) { to=mid; } else { from=mid+1; } } System.out.println(to); } static boolean f(long mid, graph G, int N, int K) { long[] d = G.dijkstra(0, mid); if (d[N-1]>=K) { return false; }else { return true; } } static class Edge implements Comparable<Edge>{ int to; long v; public Edge(int to,long v) { this.to=to; this.v=v; } @Override public boolean equals(Object obj){ if(obj instanceof Edge) { Edge other = (Edge) obj; return other.to==this.to && other.v==this.v; } return false; }//同値の定義 @Override public int hashCode() { return Objects.hash(this.to,this.v); } @Override public int compareTo( Edge p2 ){ if (this.v>p2.v) { return 1; } else if (this.v<p2.v) { return -1; } else { return 0; } } } static class graph{ ArrayList<Edge>[] list; int size; long INF=Long.MAX_VALUE/2; int[] color; @SuppressWarnings("unchecked") public graph(int n) { size = n; list = new ArrayList[n]; color =new int[n]; for(int i=0;i<n;i++){ list[i] = new ArrayList<Edge>(); } } void addEdge(int from,int to,long w) { list[from].add(new Edge(to,w)); } long[] dijkstra(int s, long b){ long[] L = new long[size]; for(int i=0;i<size;i++){ L[i] = -1; } int[] visited = new int[size]; L[s] = 0; PriorityQueue<Edge> Q = new PriorityQueue<Edge>(); Q.add(new Edge(s,0L));//Edgeに最短距離候補を持たせる while(!Q.isEmpty()){ Edge C = Q.poll(); if(visited[C.to]==0){ L[C.to] = C.v; visited[C.to] = 1; for(Edge D:list[C.to]){ if (visited[D.to]==1) { continue; } if (D.v>b) { Q.add(new Edge(D.to,L[C.to]+1)); }else { Q.add(new Edge(D.to,L[C.to])); } } } } return L; } } static class InputReader { private InputStream in; private byte[] buffer = new byte[1024]; private int curbuf; private int lenbuf; public InputReader(InputStream in) { this.in = in; this.curbuf = this.lenbuf = 0; } public boolean hasNextByte() { if (curbuf >= lenbuf) { curbuf = 0; try { lenbuf = in.read(buffer); } catch (IOException e) { throw new InputMismatchException(); } if (lenbuf <= 0) return false; } return true; } private int readByte() { if (hasNextByte()) return buffer[curbuf++]; else return -1; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private void skip() { while (hasNextByte() && isSpaceChar(buffer[curbuf])) curbuf++; } public boolean hasNext() { skip(); return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (!isSpaceChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public int nextInt() { if (!hasNext()) throw new NoSuchElementException(); int c = readByte(); while (isSpaceChar(c)) c = readByte(); boolean minus = false; if (c == '-') { minus = true; c = readByte(); } int res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res = res * 10 + c - '0'; c = readByte(); } while (!isSpaceChar(c)); return (minus) ? -res : res; } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); int c = readByte(); while (isSpaceChar(c)) c = readByte(); boolean minus = false; if (c == '-') { minus = true; c = readByte(); } long res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res = res * 10 + c - '0'; c = readByte(); } while (!isSpaceChar(c)); return (minus) ? -res : res; } public double nextDouble() { return Double.parseDouble(next()); } public int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } public double[] nextDoubleArray(int n) { double[] a = new double[n]; for (int i = 0; i < n; i++) a[i] = nextDouble(); return a; } public long[] nextLongArray(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nextLong(); return a; } public char[][] nextCharMap(int n, int m) { char[][] map = new char[n][m]; for (int i = 0; i < n; i++) map[i] = next().toCharArray(); return map; } } }