結果
問題 |
No.1382 Travel in Mitaru city
|
ユーザー |
|
提出日時 | 2022-12-01 21:26:25 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 820 bytes |
コンパイル時間 | 409 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 96,576 KB |
最終ジャッジ日時 | 2024-10-09 02:08:56 |
合計ジャッジ時間 | 18,416 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 6 WA * 62 |
ソースコード
# 常に、今まで訪れた頂点集合からいける場所のうち最も数値が小さい場所に移動する。 # heapqに、(行ける場所の数値)を入れて移動する import sys readline = sys.stdin.readline N,M,S,T = map(int,readline().split()) S -= 1 T -= 1 P = list(map(int,readline().split())) G = [[] for i in range(N)] for _ in range(M): a,b = map(int,readline().split()) G[a - 1].append(b - 1) G[b - 1].append(a - 1) import heapq as hq q = [] hq.heappush(q, (-P[S], S)) visited = [False] * N X = P[S] ans = 0 while q: p, v = hq.heappop(q) p *= (-1) if visited[v]: continue visited[v] = True if p < X: ans += 1 for child in G[v]: if visited[child]: continue hq.heappush(q, (-P[child], child)) print(ans)