結果

問題 No.2565 はじめてのおつかい
ユーザー KazunKazun
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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())
0