結果
問題 | No.1382 Travel in Mitaru city |
ユーザー |
![]() |
提出日時 | 2021-03-24 00:42:08 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 639 ms / 2,000 ms |
コード長 | 601 bytes |
コンパイル時間 | 89 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 41,456 KB |
最終ジャッジ日時 | 2024-11-26 08:27:32 |
合計ジャッジ時間 | 22,116 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 68 |
ソースコード
import heapqimport sysinput = sys.stdin.buffer.readlinesys.setrecursionlimit(10 ** 7)N, M, S, T = map(int, input().split())P = tuple(map(int, input().split()))S -= 1T -= 1G = [[] for _ in range(N)]for _ in range(M):a, b = map(int, input().split())a -= 1b -= 1G[a].append(b)G[b].append(a)seen = [0] * Nseen[S] = 1q = [(-P[S], S)]X = P[S]Y = 0while q:p, s = heapq.heappop(q)p = -pif p < X:X = pY += 1for t in G[s]:if seen[t]:continueheapq.heappush(q, (-P[t], t))seen[t] = 1print(Y)