結果

問題 No.1601 With Animals into Institute
ユーザー 👑 KazunKazun
提出日時 2021-10-11 04:20:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,977 ms / 3,000 ms
コード長 4,897 bytes
コンパイル時間 677 ms
コンパイル使用メモリ 87,152 KB
実行使用メモリ 257,560 KB
最終ジャッジ日時 2023-10-13 03:05:36
合計ジャッジ時間 29,900 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 95 ms
71,708 KB
testcase_01 AC 98 ms
71,696 KB
testcase_02 AC 96 ms
71,676 KB
testcase_03 AC 222 ms
83,120 KB
testcase_04 AC 197 ms
81,996 KB
testcase_05 AC 203 ms
82,260 KB
testcase_06 AC 1,827 ms
254,952 KB
testcase_07 AC 1,905 ms
257,560 KB
testcase_08 AC 1,852 ms
255,100 KB
testcase_09 AC 1,883 ms
245,348 KB
testcase_10 AC 1,977 ms
247,496 KB
testcase_11 AC 1,926 ms
243,880 KB
testcase_12 AC 1,853 ms
244,120 KB
testcase_13 AC 1,844 ms
246,652 KB
testcase_14 AC 1,858 ms
244,380 KB
testcase_15 AC 1,919 ms
244,588 KB
testcase_16 AC 1,898 ms
244,320 KB
testcase_17 AC 1,939 ms
243,556 KB
testcase_18 AC 214 ms
82,648 KB
testcase_19 AC 212 ms
82,600 KB
testcase_20 AC 200 ms
81,916 KB
testcase_21 AC 204 ms
82,108 KB
testcase_22 AC 200 ms
81,696 KB
testcase_23 AC 197 ms
81,892 KB
testcase_24 AC 203 ms
82,140 KB
testcase_25 AC 202 ms
81,900 KB
testcase_26 AC 196 ms
81,808 KB
testcase_27 AC 94 ms
71,672 KB
testcase_28 AC 93 ms
71,828 KB
testcase_29 AC 91 ms
71,868 KB
testcase_30 AC 92 ms
71,664 KB
testcase_31 AC 91 ms
71,888 KB
testcase_32 AC 94 ms
71,724 KB
testcase_33 AC 96 ms
71,636 KB
testcase_34 AC 95 ms
71,680 KB
testcase_35 AC 94 ms
71,864 KB
testcase_36 AC 95 ms
71,904 KB
testcase_37 AC 97 ms
71,864 KB
testcase_38 AC 98 ms
71,768 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Weigthed_Digraph:
    """重み[付き]有向グラフを生成する.

    """
    #入力定義
    def __init__(self, N):
        self.N=N
        self.arc_number=0

        self.adjacent_out=[{} for _ in range(N)] #出近傍(vが始点)
        self.adjacent_in=[{} for _ in range(N)] #入近傍(vが終点)

    #辺の追加(更新)
    def add_arc(self, source, target, weight=1):
        if target not in self.adjacent_out[source]:
            self.arc_number+=1

        self.adjacent_out[source][target]=weight
        self.adjacent_in[target][source]=weight

    #辺を除く
    def remove_arc(self, source, target):
        if self.arc_exist(source, target):
            self.arc_number+=1
            del self.adjacent_out[source][target]
            del self.adjacent_in[target][source]

    #頂点を除く
    def remove_vertex(self,*vertexes):
        pass

    #Walkの追加
    def add_walk(self,*walk):
        pass

    #Cycleの追加
    def add_cycle(self,*cycle):
        pass

    #頂点の交換
    def __vertex_swap(self,p,q):
        pass

    #グラフに辺が存在するか否か
    def arc_exist(self, source, target):
        return target in self.adjacent_out[source]

    #近傍
    def neighbohood(self,v):
        """vの出近傍, 入近傍を出力する.

        Input:
        v:頂点

        Output:
        (出近傍, 入近傍)
        """

        return (set(self.adjacent_out[v].keys()),set(self.adjacent_in[v].keys()))

    #出次数
    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.vertex)

    #辺数
    def arc_count(self):
        return self.arc_number

    #頂点vに到達可能な頂点
    def reachable_to(self,v):
        from collections import deque
        adj_in=self.adjacent_in
        T=[0]*self.N; T[v]=1
        Q=deque([v])
        while Q:
            x=Q.popleft()
            for y in adj_in[x]:
                if not T[y]:
                    T[y]=1
                    Q.append(y)
        return [x for x in range(self.N) if T[x]]

    #頂点vから到達可能な頂点
    def reachable_from(self,v):
        from collections import deque
        adj_out=self.adjacent_out
        T=[0]*self.N; T[v]=1
        Q=deque([v])
        while Q:
            x=Q.popleft()
            for y in adj_out[x]:
                if T[y]==0:
                    T[y]=1
                    Q.append(y)
        return [x for x in range(self.N) if T[x]]

    #深いコピー
    def deepcopy(self):
        from copy import deepcopy
        D=Weigthed_Digraph(self.N)
        D.arc_number=self.arc_number
        D.adjacent_out=deepcopy(self.adjacent_out)
        D.adjacent_in=deepcopy(self.adjacent_in)
        return D

def Dijkstra_All(D, start, with_path=False):
    """ Dijksta 法を用いて, 単一始点 start からの距離を求める.

    D: 辺の重みが全て非負の有向グラフ
    start: 始点, to: 終点
    with_path: 最短路も含めて出力するか?

    (出力の結果)
    with_path=True → (距離, 最短経路の辿る際の前の頂点)
    with_path=False → 距離
    """
    from heapq import heappush,heappop

    inf=float("inf")
    T=[inf]*D.N; T[start]=0

    if with_path:
        prev=[None]*D.N
        prev[start]=start

    adj_out=D.adjacent_out
    Q=[(0, start)]
    while Q:
        c,u=heappop(Q)
        if T[u]<c:
            continue

        E=adj_out[u]
        for v in E:
            if T[v]>c+E[v]:
                T[v]=c+E[v]
                heappush(Q,(T[v],v))

                if with_path:
                    prev[v]=u

    if with_path:
        return (T,prev)
    else:
        return  T

#==================================================
def encode(a,b):
    return a*10**9+b

def decode(c):
    return divmod(c,10**9)

#==================================================
from collections import defaultdict
import sys
input=sys.stdin.readline
write=sys.stdout.write

N,M=map(int,input().split())
D=Weigthed_Digraph(2*N)

inf=float("inf")
Cost=defaultdict(lambda :[inf,inf])
for _ in range(M):
    a,b,c,x=map(int,input().split())
    a-=1; b-=1

    if a>b:
        a,b=b,a

    code=encode(a,b)
    Cost[code][x]=min(Cost[code][x],c)

for code,[c0,c1] in Cost.items():
    a,b=decode(code)

    if c0!=inf:
        D.add_arc(a,b,c0)
        D.add_arc(b,a,c0)

    if c1!=inf:
        D.add_arc(a,b+N,c1)
        D.add_arc(b,a+N,c1)

    D.add_arc(a+N,b+N,min(c0,c1))
    D.add_arc(b+N,a+N,min(c0,c1))

write("\n".join(map(str,Dijkstra_All(D,N-1)[N:2*N-1])))
0