結果

問題 No.1473 おでぶなおばけさん
ユーザー FromBooskaFromBooska
提出日時 2023-04-29 17:59:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,774 ms / 2,000 ms
コード長 1,120 bytes
コンパイル時間 209 ms
コンパイル使用メモリ 82,032 KB
実行使用メモリ 274,648 KB
最終ジャッジ日時 2024-11-18 12:20:48
合計ジャッジ時間 28,751 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
54,064 KB
testcase_01 AC 46 ms
54,384 KB
testcase_02 AC 1,286 ms
228,760 KB
testcase_03 AC 776 ms
170,816 KB
testcase_04 AC 735 ms
138,924 KB
testcase_05 AC 220 ms
85,184 KB
testcase_06 AC 899 ms
172,736 KB
testcase_07 AC 1,523 ms
269,692 KB
testcase_08 AC 1,774 ms
274,648 KB
testcase_09 AC 1,260 ms
250,176 KB
testcase_10 AC 233 ms
89,280 KB
testcase_11 AC 199 ms
89,564 KB
testcase_12 AC 233 ms
89,520 KB
testcase_13 AC 153 ms
85,572 KB
testcase_14 AC 134 ms
82,056 KB
testcase_15 AC 212 ms
89,256 KB
testcase_16 AC 213 ms
89,652 KB
testcase_17 AC 93 ms
77,816 KB
testcase_18 AC 101 ms
77,496 KB
testcase_19 AC 217 ms
88,364 KB
testcase_20 AC 450 ms
120,832 KB
testcase_21 AC 360 ms
101,680 KB
testcase_22 AC 330 ms
108,580 KB
testcase_23 AC 279 ms
105,812 KB
testcase_24 AC 251 ms
103,912 KB
testcase_25 AC 1,333 ms
203,244 KB
testcase_26 AC 1,345 ms
202,420 KB
testcase_27 AC 348 ms
92,656 KB
testcase_28 AC 1,226 ms
220,948 KB
testcase_29 AC 508 ms
114,932 KB
testcase_30 AC 812 ms
146,236 KB
testcase_31 AC 1,005 ms
189,308 KB
testcase_32 AC 572 ms
134,796 KB
testcase_33 AC 514 ms
128,932 KB
testcase_34 AC 294 ms
98,088 KB
testcase_35 AC 227 ms
92,312 KB
testcase_36 AC 507 ms
111,632 KB
testcase_37 AC 793 ms
145,672 KB
testcase_38 AC 149 ms
80,492 KB
testcase_39 AC 198 ms
89,392 KB
testcase_40 AC 231 ms
89,524 KB
testcase_41 AC 218 ms
94,320 KB
testcase_42 AC 185 ms
94,192 KB
testcase_43 AC 368 ms
151,216 KB
testcase_44 AC 369 ms
150,956 KB
testcase_45 AC 368 ms
151,216 KB
testcase_46 AC 646 ms
147,088 KB
testcase_47 AC 935 ms
180,940 KB
testcase_48 AC 840 ms
187,236 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 体重何キロまで行ける、は単調なので二分探索可能
# ダイクストラでTLEしたのでBFSにする

N, M = map(int, input().split())
edge_list = []
for i in range(M):
    s, t, d = map(int, input().split())
    edge_list.append((s, t, d))

from collections import deque
INF = 10**5+2
# TLEしたのでINF下げた

def BFS(W):
    edges = [[] for i in range(N+1)]
    for s, t, d in edge_list:
        if d >= W:
            edges[s].append(t)
            edges[t].append(s)
    start = 1
    goal = N
    distance = [INF]*(N+1)  
    distance[start] = 0
    que = deque()
    que.append(start)
    while que:
        current = que.popleft()
        for nxt in edges[current]:
            if distance[nxt] > distance[current]+1:
                distance[nxt] = distance[current]+1
                que.append(nxt)
    if distance[N] == INF:
        return 0, INF
    else:
        return 1, distance[N]

OK = 0
NG = 10**9+1
while NG-OK>1:
    mid = (NG+OK)//2
    if BFS(mid)[0] == 1:
        OK = mid
    else:
        NG = mid
ans_W = OK
ans_distance = BFS(ans_W)[1]
print(ans_W, ans_distance)
0