結果

問題 No.3326 岩井星人の帰星
コンテスト
ユーザー detteiuu
提出日時 2025-11-01 15:41:59
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 630 ms / 2,000 ms
コード長 1,243 bytes
コンパイル時間 289 ms
コンパイル使用メモリ 82,368 KB
実行使用メモリ 119,644 KB
最終ジャッジ日時 2025-11-01 15:42:22
合計ジャッジ時間 20,990 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappush, heappop
from collections import deque

INF = 1<<60

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    G[u].append(v)
    G[v].append(u)
L = int(input())
JK = [list(map(int, input().split())) for _ in range(L)]

base = 10**6
def encode(d, v):
    return d*base+v
def decode(n):
    return n//base, n%base

dist = [-INF]*N
visited = [False]*N
que = []
for J, K in JK:
    J -= 1
    if dist[J] < K:
        dist[J] = K
        heappush(que, -encode(dist[J], J))

while que:
    _, n = decode(-heappop(que))
    if visited[n]:
        continue
    visited[n] = True
    if dist[n] == 0:
        continue
    for v in G[n]:
        if dist[v] < dist[n]-1:
            dist[v] = dist[n]-1
            heappush(que, -encode(dist[v], v))

if visited[0] or visited[-1]:
    exit(print("No"))

que = deque()
que.append(0)
visited2 = [-1]*N
visited2[0] = 0
while que:
    n = que.popleft()
    for v in G[n]:
        if visited[v]:
            continue
        if visited2[v] == -1:
            visited2[v] = visited2[n]+1
            que.append(v)

if visited2[-1] != -1:
    print("Yes")
    print(visited2[-1])
else:
    print("No")
0