結果

問題 No.1473 おでぶなおばけさん
ユーザー ronpooronpoo
提出日時 2023-10-31 13:52:09
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 1,044 bytes
コンパイル時間 250 ms
コンパイル使用メモリ 12,052 KB
実行使用メモリ 65,656 KB
最終ジャッジ日時 2023-10-31 13:52:45
合計ジャッジ時間 32,655 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 27 ms
10,112 KB
testcase_01 AC 28 ms
10,096 KB
testcase_02 AC 1,006 ms
62,532 KB
testcase_03 AC 596 ms
56,164 KB
testcase_04 AC 453 ms
38,828 KB
testcase_05 AC 200 ms
20,612 KB
testcase_06 AC 1,011 ms
59,712 KB
testcase_07 AC 940 ms
65,656 KB
testcase_08 AC 1,213 ms
65,656 KB
testcase_09 AC 709 ms
64,864 KB
testcase_10 AC 410 ms
49,268 KB
testcase_11 AC 812 ms
46,644 KB
testcase_12 AC 407 ms
50,356 KB
testcase_13 AC 248 ms
32,328 KB
testcase_14 AC 180 ms
26,072 KB
testcase_15 AC 415 ms
40,996 KB
testcase_16 AC 390 ms
47,512 KB
testcase_17 AC 52 ms
12,436 KB
testcase_18 AC 70 ms
14,012 KB
testcase_19 AC 603 ms
44,488 KB
testcase_20 AC 573 ms
50,860 KB
testcase_21 AC 1,364 ms
56,120 KB
testcase_22 AC 1,115 ms
54,716 KB
testcase_23 AC 1,131 ms
48,004 KB
testcase_24 AC 1,076 ms
47,504 KB
testcase_25 AC 937 ms
56,376 KB
testcase_26 AC 494 ms
58,848 KB
testcase_27 AC 220 ms
30,360 KB
testcase_28 AC 631 ms
63,212 KB
testcase_29 AC 524 ms
52,172 KB
testcase_30 AC 636 ms
59,000 KB
testcase_31 AC 818 ms
62,976 KB
testcase_32 AC 955 ms
61,492 KB
testcase_33 AC 431 ms
50,844 KB
testcase_34 AC 183 ms
31,344 KB
testcase_35 AC 326 ms
35,684 KB
testcase_36 AC 1,539 ms
47,812 KB
testcase_37 AC 434 ms
47,916 KB
testcase_38 AC 78 ms
18,384 KB
testcase_39 AC 370 ms
48,212 KB
testcase_40 AC 449 ms
48,212 KB
testcase_41 AC 344 ms
42,616 KB
testcase_42 AC 342 ms
42,664 KB
testcase_43 AC 647 ms
56,560 KB
testcase_44 AC 630 ms
56,560 KB
testcase_45 AC 636 ms
56,560 KB
testcase_46 TLE -
testcase_47 -- -
testcase_48 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
std = [list(map(int, input().split())) for _ in range(m)]

G = [[] for _ in range(n)]
D = []
W = [float('inf')] * (m+2)
for i in range(m):
    s, t, d = std[i]
    s -= 1
    t -= 1
    G[s].append((t, d))
    G[t].append((s, d))
    D.append(d)

def bfs(cost):
    dist = [float('inf')] * n
    dist[0] = 0
    q = deque([0])
    while q:
        now = q.popleft()
        for nxt, d in G[now]:            
            if dist[nxt] < dist[now] + 1:
                continue
            if d < cost:
                continue
            dist[nxt] = dist[now] + 1
            if nxt == n-1:                
                return dist[nxt]
            q.append(nxt)
    return float('inf')

D.append(0)
D.append(float('inf'))
D.sort()
ok = 0
ng = len(D)
while ng - ok > 1:
    mid = (ng + ok) // 2
    W[mid] = bfs(D[mid])
    if W[mid] != float('inf'):
        ok = mid        
    else:
        ng = mid
                
print(D[ok], W[ok])
0