結果
問題 | No.1382 Travel in Mitaru city |
ユーザー | manini |
提出日時 | 2021-02-07 21:08:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 458 ms / 2,000 ms |
コード長 | 1,040 bytes |
コンパイル時間 | 475 ms |
コンパイル使用メモリ | 86,924 KB |
実行使用メモリ | 107,432 KB |
最終ジャッジ日時 | 2023-09-17 20:06:27 |
合計ジャッジ時間 | 21,825 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 78 ms
71,380 KB |
testcase_01 | AC | 90 ms
71,172 KB |
testcase_02 | AC | 80 ms
71,144 KB |
testcase_03 | AC | 90 ms
71,188 KB |
testcase_04 | AC | 82 ms
71,128 KB |
testcase_05 | AC | 80 ms
71,008 KB |
testcase_06 | AC | 252 ms
92,056 KB |
testcase_07 | AC | 233 ms
88,264 KB |
testcase_08 | AC | 199 ms
83,792 KB |
testcase_09 | AC | 260 ms
92,340 KB |
testcase_10 | AC | 252 ms
91,628 KB |
testcase_11 | AC | 310 ms
93,472 KB |
testcase_12 | AC | 337 ms
94,288 KB |
testcase_13 | AC | 355 ms
95,576 KB |
testcase_14 | AC | 311 ms
92,892 KB |
testcase_15 | AC | 302 ms
93,220 KB |
testcase_16 | AC | 398 ms
101,388 KB |
testcase_17 | AC | 395 ms
101,688 KB |
testcase_18 | AC | 405 ms
101,784 KB |
testcase_19 | AC | 397 ms
101,400 KB |
testcase_20 | AC | 389 ms
101,468 KB |
testcase_21 | AC | 417 ms
101,728 KB |
testcase_22 | AC | 413 ms
101,500 KB |
testcase_23 | AC | 418 ms
101,916 KB |
testcase_24 | AC | 392 ms
101,520 KB |
testcase_25 | AC | 393 ms
101,728 KB |
testcase_26 | AC | 420 ms
102,048 KB |
testcase_27 | AC | 430 ms
101,692 KB |
testcase_28 | AC | 436 ms
101,932 KB |
testcase_29 | AC | 431 ms
101,828 KB |
testcase_30 | AC | 389 ms
101,424 KB |
testcase_31 | AC | 275 ms
96,876 KB |
testcase_32 | AC | 312 ms
100,648 KB |
testcase_33 | AC | 301 ms
99,072 KB |
testcase_34 | AC | 243 ms
92,512 KB |
testcase_35 | AC | 203 ms
88,412 KB |
testcase_36 | AC | 233 ms
97,364 KB |
testcase_37 | AC | 139 ms
82,004 KB |
testcase_38 | AC | 244 ms
99,840 KB |
testcase_39 | AC | 145 ms
80,936 KB |
testcase_40 | AC | 210 ms
93,760 KB |
testcase_41 | AC | 221 ms
95,600 KB |
testcase_42 | AC | 239 ms
99,568 KB |
testcase_43 | AC | 225 ms
96,340 KB |
testcase_44 | AC | 162 ms
85,352 KB |
testcase_45 | AC | 218 ms
94,720 KB |
testcase_46 | AC | 230 ms
86,772 KB |
testcase_47 | AC | 429 ms
105,816 KB |
testcase_48 | AC | 355 ms
97,988 KB |
testcase_49 | AC | 458 ms
107,432 KB |
testcase_50 | AC | 288 ms
91,292 KB |
testcase_51 | AC | 274 ms
97,292 KB |
testcase_52 | AC | 342 ms
100,692 KB |
testcase_53 | AC | 169 ms
84,004 KB |
testcase_54 | AC | 211 ms
89,716 KB |
testcase_55 | AC | 295 ms
99,768 KB |
testcase_56 | AC | 167 ms
84,812 KB |
testcase_57 | AC | 239 ms
92,952 KB |
testcase_58 | AC | 153 ms
81,324 KB |
testcase_59 | AC | 180 ms
86,044 KB |
testcase_60 | AC | 290 ms
99,008 KB |
testcase_61 | AC | 113 ms
77,828 KB |
testcase_62 | AC | 78 ms
71,056 KB |
testcase_63 | AC | 146 ms
79,784 KB |
testcase_64 | AC | 114 ms
77,984 KB |
testcase_65 | AC | 97 ms
76,416 KB |
testcase_66 | AC | 118 ms
77,736 KB |
testcase_67 | AC | 118 ms
77,792 KB |
testcase_68 | AC | 120 ms
77,900 KB |
testcase_69 | AC | 116 ms
77,844 KB |
testcase_70 | AC | 123 ms
77,812 KB |
ソースコード
# coding:UTF-8 import sys from heapq import heappush, heappop MOD = 10 ** 9 + 7 INF = float('inf') N, M, S, T = list(map(int, input().split())) # スペース区切り連続数字 P = list(map(int, input().split())) # スペース区切り連続数字 AB = [list(map(int, input().split())) for _ in range(M)] # スペース区切り連続数字(行列) dist = [[] for _ in range(N)] # dist[n]: ノード n に隣接する(ノード, 重み)をリストで持つ for a, b in AB: dist[a-1].append(b-1) dist[b-1].append(a-1) # 双方向の場合追加する Y = 0 X = P[S-1] hq = [(-P[S-1], S-1)] # (distance, node) seen = [False] * N # ノードが確定済みかどうか seen[S-1] = True while hq: d, v = heappop(hq) # ノードを pop する d = -d if d < X: X = d Y += 1 for to in dist[v]: # ノード v に隣接しているノードに対して if seen[to] == False: heappush(hq, (-P[to], to)) seen[to] = True print("{}".format(Y))