結果
問題 | No.3093 Safe Infection |
ユーザー |
|
提出日時 | 2025-03-05 17:36:00 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 435 ms / 2,000 ms |
コード長 | 700 bytes |
コンパイル時間 | 515 ms |
コンパイル使用メモリ | 82,732 KB |
実行使用メモリ | 109,976 KB |
最終ジャッジ日時 | 2025-03-05 17:36:21 |
合計ジャッジ時間 | 19,929 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 70 |
ソースコード
from heapq import * N,M,K=map(int,input().split()) A=list(map(int,input().split())) G=[set() for i in range(N)] for i in range(M): u,v=map(int,input().split()) G[u-1].add(v-1) G[v-1].add(u-1) mi=10**10 argmin=0 for i in range(N): if A[i]<mi: argmin=i mi=A[i] dist=[False]*N que=[] for nv in G[argmin]: heappush(que,(A[nv],nv)) dist[argmin]=True now=mi while (len(que)): val,v=heappop(que) if dist[v]: continue dist[v]=True if val-now>K: print('No') break now=val for nv in G[v]: if dist[nv]: continue heappush(que,(A[nv],nv)) else: print('Yes')