結果

問題 No.3326 岩井星人の帰星
コンテスト
ユーザー Prala
提出日時 2025-11-01 16:29:50
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,072 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 426 ms
コンパイル使用メモリ 82,308 KB
実行使用メモリ 164,208 KB
最終ジャッジ日時 2025-11-01 16:30:12
合計ジャッジ時間 19,738 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29 RE * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
sys.setrecursionlimit(5*10**7)
import math
import bisect
import heapq
from collections import deque, defaultdict 
import random
import itertools
#from decimal import Decimal
#from copy import copy, deepcopy

# -------------------------------------------------
pin = sys.stdin.readline
def ST(): return pin().rstrip()
def IN(): return int(pin())
def IM(): return map(int, pin().split())
def IL(): return list(IM())
def SR(n:int)->list: return [pin().rstrip() for _ in range(n)]
def IMatrix(n:int)->list: return [IL() for _ in range(n)]

INF = 2*10**18+1
mod = 998244353
# -------------------------------------------------
#import pypyjit
#pypyjit.set_param("max_unroll_recursion=-1")

def BFS_basic(G, a): # グラフGの頂点aを始点とする幅優先探索
    dist = [-1] * len(G)
    nodes = [[] for _ in range(len(G))]
    dist[a] = 0
    nodes[0] = [a]
    for k in range(1, len(G)): # k-1 手目に探索された各頂点 v に対して
        for v in nodes[k - 1]:
            for next_v in G[v]: # 頂点 next_v を探索する
                if dist[next_v] == -1:
                    dist[next_v] = dist[v] + 1
                    nodes[k].append(next_v)
    return dist, nodes

N, M = IM()
G = [set() for _ in range(N)]

for _ in range(M):
    a, b = IM()
    a -= 1
    b -= 1
    G[a].add(b)
    G[b].add(a)

nodes = [[] for _ in range(1001)]
seen = [0]*N
L = IN()

for _ in range(L):
    j, k = IM()
    nodes[1000-k].append(j-1)

for i in range(1000):
    if not nodes[i]:
        continue
    for v in nodes[i]:
        if seen[v]:
            continue
        seen[v] = 1
        for next_v in G[v]:
            if seen[next_v]:
                continue
            nodes[i+1].append(next_v)

for i in nodes[1000]:
    seen[i] = 1

for j in range(N):
    if seen[j]:
        G[j] = set()
        continue
    for i in G[j]:
        ng = set()
        if seen[i]:
            ng.add(i)
    G[j] -= ng

dist, _ = BFS_basic(G, 0)

if dist[N-1] == -1:
    print("No")
elif seen[0]:
    print("No")
else:
    print("Yes")
    print(dist[N-1])
0