結果

問題 No.3326 岩井星人の帰星
コンテスト
ユーザー あじゃじゃ
提出日時 2025-03-06 09:11:09
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,080 bytes
コンパイル時間 320 ms
コンパイル使用メモリ 82,096 KB
実行使用メモリ 126,704 KB
最終ジャッジ日時 2025-11-01 09:26:04
合計ジャッジ時間 19,406 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51 TLE * 1 -- * 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=[]
jk=[]
for _ in range(l):
    jk.append(tuple(map(int,input().split())))
jk.sort(reverse=True,key=lambda x:x[-1])
for i in range(l):
    j,k=jk[i]
    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
if dist[0]>=0:
    exit(print("No"))
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