結果

問題 No.2780 The Bottle Imp
コンテスト
ユーザー のーと
提出日時 2024-07-10 15:37:52
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,674 bytes
コンパイル時間 373 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 28,032 KB
最終ジャッジ日時 2024-07-10 15:38:04
合計ジャッジ時間 12,197 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 36 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

N=int(input())

def minus1(L):#入力前に
  return [l-1 for l in L]
def emp_graph(N):#長さNの空の隣接リスト
  return [[] for i in range(N)]
 
graph=emp_graph(N)
  
for i in range(N):
	L=minus1(list(map(int,input().split())))
	M=L[0]
	A=L[1:]
	for a in A:
		graph[i].append(a)

#print(graph)

from collections import deque
import sys
sys.setrecursionlimit(10**5) #ここまでは共通
def bfs(graph,start):#隣接リストgraphの頂点startから各点までの最短距離(デフォ-1)のリストdistを返す
  """
  各辺がつなぐ2つの頂点をa,bとする
  →隣接リストgraphにa→bなど入れる
  ※有向グラフなら片方から、無向グラフなら両側から入れる
  """
  dist = [-1]*len(graph) #各頂点の最短距離のリスト(これが求めるもの。デフォは-1)
  dist[start] = 0 #最初の出発地は0にする
  d=deque()
  d.append(start) #最初の出発地を入れる
  
  """
  目的地になったが出発地になっていない頂点のdeque
  「先頭から要素を取り出す」「末尾に要素を追加する」ためdeque使用
  """
  
  while len(d)>0: # (出発地,目的地)
   i = d.popleft() #dの一番[左]は今から出発地になる
   for j in graph[i]: #その頂点に直接つながる各頂点[目]について
     if dist[j] != -1: #[目]に訪問済みなら
       continue #スキップ
     dist[j] = dist[i] + 1 #でなければ(未訪問なら直ちに)最短距離をdistに記録（目的地になった）
     d.append(j) #dの[右]に、出発地未経験の頂点を追加
  return dist

dist=bfs(graph,0)#普通の場合
print("No" if -1 in dist else "Yes")
0