結果

問題 No.1601 With Animals into Institute
コンテスト
ユーザー 👑 Kazun
提出日時 2021-10-11 04:20:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,977 ms / 3,000 ms
コード長 4,897 bytes
コンパイル時間 298 ms
コンパイル使用メモリ 81,664 KB
実行使用メモリ 252,248 KB
最終ジャッジ日時 2024-09-15 00:45:15
合計ジャッジ時間 29,163 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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