結果

問題 No.859 路線A、路線B、路線C
ユーザー KazunKazun
提出日時 2021-01-29 18:38:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 42 ms / 1,000 ms
コード長 3,992 bytes
コンパイル時間 271 ms
コンパイル使用メモリ 82,264 KB
実行使用メモリ 53,888 KB
最終ジャッジ日時 2024-06-27 05:20:10
合計ジャッジ時間 1,693 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
53,632 KB
testcase_01 AC 41 ms
53,440 KB
testcase_02 AC 42 ms
53,248 KB
testcase_03 AC 42 ms
53,888 KB
testcase_04 AC 41 ms
53,248 KB
testcase_05 AC 41 ms
53,632 KB
testcase_06 AC 42 ms
53,632 KB
testcase_07 AC 41 ms
53,760 KB
testcase_08 AC 42 ms
53,504 KB
testcase_09 AC 41 ms
53,504 KB
testcase_10 AC 41 ms
53,248 KB
testcase_11 AC 41 ms
53,504 KB
testcase_12 AC 41 ms
53,248 KB
testcase_13 AC 41 ms
53,504 KB
testcase_14 AC 42 ms
53,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Weigthed_Graph:
    #入力定義
    def __init__(self,vertex=[]):
        self.adjacent={v:{} for v in vertex}

    #頂点の追加
    def add_vertex(self,*adder):
        for u in adder:
            if u not in self.adjacent:
                self.adjacent[u]={}

    #辺の追加
    def add_edge(self,u,v,Weight):
        if u not in self.adjacent:self.add_vertex(u)
        if v not in self.adjacent:self.add_vertex(v)

        self.adjacent[u][v]=Weight
        self.adjacent[v][u]=Weight

    #辺を除く
    def remove_edge(self,u,v):
        for w in [u,v]:
            if w not in self.adjacent:
                self.add_vertex(w)

        try:
            del self.adjacent[u][v]
            del self.adjacent[v][u]
        except:
            pass

    #頂点を除く
    def remove_vertex(self,*v):
        for u in v:
            for w in self.vertex:
                try:
                    del self.adjacent[w][u]
                except:
                    pass
            del self.adjacent[u]
    #Walkの追加

    #Cycleの追加

    #頂点の交換

    #グラフに頂点が存在するか否か
    def vertex_exist(self,v):
        try:
            _=self.adjacent[v]
            return True
        except:
            return False

    #グラフに辺が存在するか否か
    def edge_exist(self,u,v):
        return v in self.adjacent[u]

    #出近傍
    def in_neighbohood(self,v):
        try:
            return list(self.adjacent[v].keys())
        except:
            return None

    #出次数
    def in_degree(self,v):
        try:
            return len(self.adjacent[v])
        except:
            pass


    #頂点数
    def vertex_count(self):
        return len(self.adjacent)

    #辺数

    #頂点vを含む連結成分

    #距離

    #最短路

#Dijkstra
def Dijkstra(G,From,To,with_path=False):
    """Dijksta法を用いて,FromからToまでの距離を求める.

    G:辺の重みが全て非負の無向グラフ
    From:始点
    To:終点
    with_path:最短路も含めて出力するか?

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

    inf=float("inf")
    T={v:inf for v in G.adjacent}
    T[From]=0

    if with_path:
        Prev={v:None for v in G.adjacent}

    Q=[(0,From)]

    Flag=False
    while Q:
        c,u=heappop(Q)

        if u==To:
            Flag=True
            break

        if T[u]<c:
            continue

        E=G.adjacent[u]
        for v in E:
            p=T[u]+E[v]
            if T[v]>p:
                T[v]=p
                heappush(Q,(p,v))

                if with_path:
                    Prev[v]=u

    if not Flag:
        if with_path:
            return (inf,None)
        else:
            return inf

    if with_path:
        path=[To]
        u=To
        while (Prev[u]!=None):
            u=Prev[u]
            path.append(u)
        return (T[To],path[::-1])
    else:
        return T[To]
#================================================
x,y,z=map(int,input().split())
A,B,C="ABC"

D=Weigthed_Graph()
D.add_edge((A,1),(A,x),x-1)
D.add_edge((B,1),(B,y),y-1)
D.add_edge((C,1),(C,z),z-1)

D.add_edge((A,1),(B,1),1)
D.add_edge((B,1),(C,1),1)
D.add_edge((C,1),(A,1),1)

D.add_edge((A,x),(B,y),1)
D.add_edge((B,y),(C,z),1)
D.add_edge((C,z),(A,x),1)

S,s=input().split();s=int(s)
if S==A:
    D.add_edge((A,1),(A,s),s-1)
    D.add_edge((A,s),(A,x),x-s)
elif S==B:
    D.add_edge((B,1),(B,s),s-1)
    D.add_edge((B,s),(B,y),y-s)
else:
    D.add_edge((C,1),(C,s),s-1)
    D.add_edge((C,s),(C,z),z-s)

T,t=input().split();t=int(t)
if T==A:
    D.add_edge((A,1),(A,t),t-1)
    D.add_edge((A,t),(A,x),x-t)
elif T==B:
    D.add_edge((B,1),(B,t),t-1)
    D.add_edge((B,t),(B,y),y-t)
else:
    D.add_edge((C,1),(C,t),t-1)
    D.add_edge((C,t),(C,z),z-t)

if S==T:
    D.add_edge((S,s),(T,t),abs(s-t))

print(Dijkstra(D,(S,s),(T,t)))
0