結果

問題 No.1601 With Animals into Institute
ユーザー 👑 KazunKazun
提出日時 2021-10-11 04:10:32
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,744 bytes
コンパイル時間 296 ms
コンパイル使用メモリ 87,092 KB
実行使用メモリ 269,272 KB
最終ジャッジ日時 2023-10-13 02:55:43
合計ジャッジ時間 36,888 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 94 ms
71,924 KB
testcase_01 AC 93 ms
71,784 KB
testcase_02 AC 93 ms
71,692 KB
testcase_03 AC 224 ms
84,060 KB
testcase_04 AC 199 ms
83,140 KB
testcase_05 AC 205 ms
83,100 KB
testcase_06 AC 2,288 ms
267,992 KB
testcase_07 AC 2,375 ms
267,984 KB
testcase_08 AC 2,151 ms
267,620 KB
testcase_09 AC 2,201 ms
268,104 KB
testcase_10 AC 2,553 ms
268,248 KB
testcase_11 AC 2,197 ms
268,456 KB
testcase_12 AC 2,220 ms
269,096 KB
testcase_13 AC 2,332 ms
269,004 KB
testcase_14 AC 2,187 ms
267,808 KB
testcase_15 AC 2,237 ms
269,272 KB
testcase_16 AC 2,250 ms
267,832 KB
testcase_17 AC 2,168 ms
267,744 KB
testcase_18 AC 213 ms
83,080 KB
testcase_19 AC 211 ms
83,628 KB
testcase_20 AC 209 ms
82,856 KB
testcase_21 WA -
testcase_22 AC 209 ms
82,852 KB
testcase_23 AC 207 ms
82,944 KB
testcase_24 AC 207 ms
83,972 KB
testcase_25 AC 204 ms
83,044 KB
testcase_26 AC 208 ms
82,856 KB
testcase_27 AC 94 ms
71,788 KB
testcase_28 AC 95 ms
71,968 KB
testcase_29 AC 93 ms
71,704 KB
testcase_30 WA -
testcase_31 AC 97 ms
71,740 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 AC 95 ms
71,848 KB
testcase_35 AC 94 ms
71,912 KB
testcase_36 AC 96 ms
71,716 KB
testcase_37 WA -
testcase_38 AC 94 ms
71,688 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

#==================================================
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)
for _ in range(M):
    a,b,c,x=map(int,input().split())
    a-=1; b-=1

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

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

for (a,b,x),c in Cost.items():
    if x==0:
        D.add_arc(a,b,c)
        D.add_arc(b,a,c)
        D.add_arc(a+N,b+N,c)
        D.add_arc(b+N,a+N,c)
    else:
        D.add_arc(a,b+N,c)
        D.add_arc(b,a+N,c)
        D.add_arc(a+N,b+N,c)
        D.add_arc(b+N,a+N,c)

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