結果
| 問題 | No.2565 はじめてのおつかい |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2024-01-21 12:07:22 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,016 ms / 2,000 ms |
| コード長 | 7,464 bytes |
| コンパイル時間 | 298 ms |
| コンパイル使用メモリ | 82,704 KB |
| 実行使用メモリ | 303,084 KB |
| 最終ジャッジ日時 | 2024-09-28 06:14:10 |
| 合計ジャッジ時間 | 25,299 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 43 ms
55,248 KB |
| testcase_01 | AC | 46 ms
56,008 KB |
| testcase_02 | AC | 43 ms
55,772 KB |
| testcase_03 | AC | 1,016 ms
302,704 KB |
| testcase_04 | AC | 662 ms
303,084 KB |
| testcase_05 | AC | 45 ms
55,100 KB |
| testcase_06 | AC | 461 ms
121,116 KB |
| testcase_07 | AC | 254 ms
98,880 KB |
| testcase_08 | AC | 273 ms
110,984 KB |
| testcase_09 | AC | 414 ms
113,688 KB |
| testcase_10 | AC | 343 ms
118,408 KB |
| testcase_11 | AC | 705 ms
190,912 KB |
| testcase_12 | AC | 170 ms
85,156 KB |
| testcase_13 | AC | 316 ms
112,212 KB |
| testcase_14 | AC | 524 ms
153,804 KB |
| testcase_15 | AC | 526 ms
142,632 KB |
| testcase_16 | AC | 579 ms
206,324 KB |
| testcase_17 | AC | 165 ms
96,492 KB |
| testcase_18 | AC | 217 ms
119,892 KB |
| testcase_19 | AC | 638 ms
175,324 KB |
| testcase_20 | AC | 578 ms
167,108 KB |
| testcase_21 | AC | 559 ms
168,092 KB |
| testcase_22 | AC | 320 ms
130,992 KB |
| testcase_23 | AC | 391 ms
137,644 KB |
| testcase_24 | AC | 111 ms
82,352 KB |
| testcase_25 | AC | 577 ms
169,960 KB |
| testcase_26 | AC | 381 ms
131,388 KB |
| testcase_27 | AC | 534 ms
174,596 KB |
| testcase_28 | AC | 598 ms
169,384 KB |
| testcase_29 | AC | 727 ms
201,904 KB |
| testcase_30 | AC | 566 ms
179,428 KB |
| testcase_31 | AC | 600 ms
170,708 KB |
| testcase_32 | AC | 316 ms
128,316 KB |
| testcase_33 | AC | 535 ms
176,724 KB |
| testcase_34 | AC | 564 ms
158,980 KB |
| testcase_35 | AC | 609 ms
197,580 KB |
| testcase_36 | AC | 605 ms
180,212 KB |
| testcase_37 | AC | 371 ms
135,304 KB |
| testcase_38 | AC | 511 ms
155,192 KB |
| testcase_39 | AC | 511 ms
143,860 KB |
| testcase_40 | AC | 648 ms
193,180 KB |
| testcase_41 | AC | 695 ms
209,392 KB |
| testcase_42 | AC | 366 ms
128,092 KB |
| testcase_43 | AC | 458 ms
151,872 KB |
| testcase_44 | AC | 289 ms
114,572 KB |
| testcase_45 | AC | 166 ms
97,176 KB |
| testcase_46 | AC | 561 ms
145,464 KB |
| testcase_47 | AC | 358 ms
104,896 KB |
| testcase_48 | AC | 334 ms
113,352 KB |
| testcase_49 | AC | 170 ms
85,728 KB |
| testcase_50 | AC | 424 ms
112,792 KB |
| testcase_51 | AC | 46 ms
55,372 KB |
| testcase_52 | AC | 230 ms
111,368 KB |
ソースコード
class Digraph:
"""重み[なし]有向グラフを生成する.
"""
#入力定義
def __init__(self, N=0):
""" N 頂点の空グラフを生成する. """
self.arc_number=0
self.adjacent_out=[set() for v in range(N)]#出近傍(vが始点)
self.adjacent_in=[set() for v in range(N)] #入近傍(vが終点)
#頂点の追加
def add_vertex(self):
""" 頂点を追加する.
"""
self.adjacent_out.append(set())
self.adjacent_in.append(set())
return self.order()-1
def add_vertices(self, k=1):
""" 頂点を k 個追加する.
k: int
"""
n=self.order()
self.adjacent_out.extend([set() for _ in range(k)])
self.adjacent_in.extend([set() for _ in range(k)])
return list(range(n,n+k))
#辺の追加
def add_arc(self, source, target, mode=0):
if target not in self.adjacent_out[source]:
self.adjacent_out[source].add(target)
self.adjacent_in[target].add(source)
self.arc_number+=1
if mode:
return self.arc_number-1
else:
if mode:
return -1
#辺を除く
def remove_arc(self, source, target):
if target in self.adjacent_out[source]:
self.adjacent_out[source].discard(target)
self.adjacent_in[target].discard(source)
self.arc_number-=1
def reset_vertex(self, u):
""" 頂点 u に接続している辺を全て消す."""
X=self.adjacent_out[u].copy()
for v in X:
self.remove_arc(u,v)
X=self.adjacent_in[u].copy()
for w in X:
self.remove_arc(w,u)
#Walkの追加
def add_walk(self,*walk):
""" 有向歩道 walk=(w[0], ..., w[n-1]) を追加する. """
N=len(walk)
for k in range(N-1):
self.add_arc(walk[k],walk[k+1])
#Cycleの追加
def add_cycle(self,*cycle):
""" 有向サイクル cycle=(c[0] ..., c[n-1]) を追加する. """
self.add_walk(*cycle)
self.add_arc(cycle[-1],cycle[0])
#グラフに辺が存在するか否か
def arc_exist(self, u, v):
""" 有向辺 u -> v は存在するか? """
return (v in self.adjacent_out[u])
#近傍
def neighbohood(self,v):
"""vの出近傍, 入近傍を出力する.
Input:
v:頂点
Output:
(出近傍, 入近傍)
"""
return (self.adjacent_out[v],self.adjacent_in[v])
#出次数
def out_degree(self,v):
return len(self.adjacent_out[v])
#入次数
def in_degree(self,v):
return len(self.adjacent_in[v])
#次数
def degree(self,v):
return (self.out_degree(v),self.in_degree(v))
#相対次数
def relative_degree(self,v):
return self.out_degree(v)-self.in_degree(v)
#頂点数
def vertex_count(self):
""" グラフの頂点数 (位数) を求める."""
return len(self.adjacent_out)
def order(self):
""" グラフの位数 (頂点数) を求める."""
return len(self.adjacent_out)
#辺数
def arc_count(self):
""" グラフの辺数 (サイズ) を求める."""
return self.arc_number
def size(self):
""" グラフのサイズ (辺数) を求める. """
return self.arc_number
#頂点vに到達可能な頂点
def reachable_to(self,v):
""" 頂点 v に到達可能な頂点を求める. """
from collections import deque
N=self.vertex_count()
T=[0]*N; T[v]=1
Q=deque([v])
while Q:
x=Q.pop()
for y in self.adjacent_in[x]:
if not T[y]:
T[y]=1
Q.append(y)
return [x for x in range(N) if T[x]]
#頂点vから到達可能な頂点
def reachable_from(self,v):
""" 頂点 v へ到達可能な頂点を求める. """
from collections import deque
N=self.vertex_count()
T=[0]*N; T[v]=1
Q=deque([v])
while Q:
x=Q.pop()
for y in self.adjacent_out[x]:
if not T[y]:
T[y]=1
Q.append(y)
return [x for x in range(N) if T[x]]
#頂点 u,v の距離を求める.
def distance(self,u,v):
if u==v:
return 0
from collections import deque
inf=float("inf")
N=self.vertex_count()
adj_out=self.adjacent_out
T=[inf]*N; T[u]=0
Q=deque([u])
while Q:
w=Q.popleft()
for x in adj_out[w]:
if T[x]==inf:
T[x]=T[w]+1
Q.append(x)
if x==v:
return T[x]
return inf
#ある1点からの距離
def distance_all(self,u):
""" 頂点 u からの距離を求める."""
from collections import deque
inf=float("inf")
adj_out=self.adjacent_out
T=[inf]*self.vertex_count(); T[u]=0
Q=deque([u])
while Q:
w=Q.popleft()
for x in adj_out[w]:
if T[x]==inf:
T[x]=T[w]+1
Q.append(x)
return T
def shortest_path(self,u,v, dist=False):
""" u から v への最短路を求める (存在しない場合は None).
dist: False → shortest_path のみ, True → (dist, shortest_path)"""
if u==v:
if dist:
return (0,[u])
else:
return [u]
from collections import deque
inf=float("inf")
adj_in=self.adjacent_in
T=[-1]*self.vertex_count()
Q=deque([v]); T[v]=v
while Q:
w=Q.popleft()
for x in adj_in[w]:
if T[x]==-1:
T[x]=w
Q.append(x)
if x==u:
P=[u]
a=u
while a!=v:
a=T[a]
P.append(a)
if dist:
return (len(P)-1,P)
else:
return P
if dist:
return (inf,None)
else:
return None
#深いコピー
def deepcopy(self):
from copy import deepcopy
D=Digraph(self.vertex_count())
D.arc_number=self.arc_count()
D.adjacent_out=deepcopy(self.adjacent_out)
D.adjacent_in=deepcopy(self.adjacent_in)
return D
#==================================================
def solve():
N, M = map(int, input().split())
def encode(x, p, q):
return (2 * p + q) * N + (x - 1)
D = Digraph(4 * N)
for j in range(M):
u, v = map(int, input().split())
if v == N - 1:
a, b = 1, 0
elif v == N:
a, b = 0, 1
else:
a, b = 0, 0
for p, q in [(0, 0), (0, 1), (1, 0), (1, 1)]:
D.add_arc(encode(u, p, q), encode(v, p | a, q | b))
dist = D.distance(encode(1, 0, 0), encode(1, 1, 1))
return dist if dist < float('inf') else -1
#==================================================
import sys
input=sys.stdin.readline
write=sys.stdout.write
print(solve())