結果

問題 No.3326 岩井星人の帰星
コンテスト
ユーザー あじゃじゃ
提出日時 2025-03-06 09:04:17
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 949 bytes
コンパイル時間 211 ms
コンパイル使用メモリ 82,796 KB
実行使用メモリ 137,268 KB
最終ジャッジ日時 2025-11-01 09:26:27
合計ジャッジ時間 47,314 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47 TLE * 5 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
from heapq import *
n,m=map(int,input().split())
g=[[]for _ in range(n)]

for _ in range(m):
    u,v=map(int,input().split())
    u-=1
    v-=1
    g[u].append(v)
    g[v].append(u)
l=int(input())
dist=[-1]*n
hq=[]
for _ in range(l):
    j,k=map(int,input().split())
    j-=1
    if dist[j]>k:continue
    dist[j]=k
    heappush(hq,(-dist[j],j))
    while hq:
        cost,now=heappop(hq)
        cost=-cost
        if cost<dist[now]:continue
        if cost==0:continue
        for nxt in g[now]:
            if dist[nxt]<cost-1 :
                dist[nxt]=cost-1
                heappush(hq,(-dist[nxt],nxt))

can_reach=[-1]*n
can_reach[0]=0
q=deque()
q.append(0)
while q:
    now=q.popleft()
    for nxt in g[now]:
        if can_reach[nxt]>=0 or dist[nxt]>=0:continue
        can_reach[nxt]=can_reach[now]+1
        q.append(nxt)

if can_reach[-1]>=0:
    print("Yes")
    print(can_reach[-1])
else:
    print("No")
0