結果
問題 | No.1473 おでぶなおばけさん |
ユーザー | O2MT |
提出日時 | 2021-06-02 00:53:09 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,188 bytes |
コンパイル時間 | 323 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 125,312 KB |
最終ジャッジ日時 | 2024-04-26 09:58:02 |
合計ジャッジ時間 | 19,728 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
53,888 KB |
testcase_01 | AC | 42 ms
54,144 KB |
testcase_02 | AC | 652 ms
111,848 KB |
testcase_03 | AC | 383 ms
104,856 KB |
testcase_04 | AC | 430 ms
92,936 KB |
testcase_05 | AC | 178 ms
80,640 KB |
testcase_06 | AC | 634 ms
101,128 KB |
testcase_07 | AC | 637 ms
106,088 KB |
testcase_08 | AC | 918 ms
108,256 KB |
testcase_09 | AC | 545 ms
105,832 KB |
testcase_10 | AC | 207 ms
83,968 KB |
testcase_11 | AC | 233 ms
84,148 KB |
testcase_12 | AC | 179 ms
84,208 KB |
testcase_13 | AC | 158 ms
81,408 KB |
testcase_14 | AC | 119 ms
79,104 KB |
testcase_15 | AC | 203 ms
83,968 KB |
testcase_16 | AC | 160 ms
82,988 KB |
testcase_17 | AC | 84 ms
77,440 KB |
testcase_18 | AC | 91 ms
77,440 KB |
testcase_19 | AC | 212 ms
84,736 KB |
testcase_20 | AC | 319 ms
107,040 KB |
testcase_21 | AC | 388 ms
96,540 KB |
testcase_22 | AC | 266 ms
123,204 KB |
testcase_23 | AC | 249 ms
122,624 KB |
testcase_24 | AC | 246 ms
115,816 KB |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | AC | 661 ms
107,912 KB |
testcase_29 | AC | 416 ms
98,900 KB |
testcase_30 | AC | 576 ms
101,276 KB |
testcase_31 | AC | 550 ms
125,312 KB |
testcase_32 | AC | 487 ms
108,988 KB |
testcase_33 | AC | 385 ms
103,288 KB |
testcase_34 | AC | 228 ms
93,144 KB |
testcase_35 | AC | 185 ms
88,288 KB |
testcase_36 | AC | 290 ms
93,412 KB |
testcase_37 | AC | 550 ms
100,568 KB |
testcase_38 | AC | 121 ms
78,972 KB |
testcase_39 | AC | 161 ms
83,584 KB |
testcase_40 | AC | 162 ms
82,944 KB |
testcase_41 | AC | 221 ms
87,728 KB |
testcase_42 | AC | 169 ms
88,112 KB |
testcase_43 | AC | 212 ms
102,248 KB |
testcase_44 | AC | 214 ms
102,436 KB |
testcase_45 | AC | 213 ms
102,528 KB |
testcase_46 | AC | 293 ms
105,216 KB |
testcase_47 | AC | 362 ms
108,900 KB |
testcase_48 | AC | 349 ms
107,884 KB |
ソースコード
from collections import deque def is_ok(w): # 条件を満たすかどうか?問題ごとに定義 que = deque([(0,0)]) visited = [float('inf')]*N visited[0] = 0 while que: t,c = que.popleft() for i,j in l[t]: if w > j or c+1 >= visited[i]: continue visited[i] = c+1 que.append((i,c+1)) if visited[-1] == float('inf'): visited[-1] = -1 return visited[-1] def meguru_bisect(ng, ok): ''' 初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す まずis_okを定義すべし ng ok は とり得る最小の値-1 とり得る最大の値+1 最大最小が逆の場合はよしなにひっくり返す ''' num = 0 while (abs(ok - ng) > 1): mid = (ok + ng) // 2 flg = is_ok(mid) if flg != -1: ng = mid num = flg else: ok = mid return (ng,num) N,M = map(int,input().split()) l = [[] for _ in range(N)] for _ in range(M): a,b,c = map(int,input().split()) a -= 1 b -= 1 l[a].append((b,c)) l[b].append((a,c)) ng,ok = 0,10**9 ans = meguru_bisect(ng,ok) print(ans[0],ans[1])