結果

問題 No.859 路線A、路線B、路線C
コンテスト
ユーザー simamumu
提出日時 2019-08-09 21:57:40
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 36 ms / 1,000 ms
コード長 1,915 bytes
コンパイル時間 75 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 11,776 KB
最終ジャッジ日時 2024-07-19 11:48:38
合計ジャッジ時間 1,198 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

X,Y,Z = inpl()
Ss,Si = input().split()
Ts,Ti = input().split()
Si,Ti = int(Si),int(Ti)

if Si > Ti:
    Si,Ti = Ti,Si
    Ss,Ts = Ts,Ss

def dijkstra(lines,N,s):
    weight = [INF]*N
    weight[s] = 0

    def search(s,w_0,q,weight):
        for t,w in lines[s]:
            w += w_0
            if weight[t] > w:
                heapq.heappush(q,[w,t])
                weight[t] = w

    q = [[0,s]]
    heapq.heapify(q)
    while q:
        w,n = heapq.heappop(q)
        search(n,w,q,weight)

    return weight

lines = defaultdict(set)
N = 8
if Ss == 'A' and Ts == 'A':
    lines[1].add((0,Si-1))
    lines[0].add((7,Ti-Si))
    lines[7].add((2,X-Ti))
elif Ss == 'A':
    lines[1].add((0,Si-1))
    lines[0].add((2,X-Si))
elif Ts == 'A':
    lines[1].add((7,Ti-1))
    lines[7].add((2,X-Ti))

if Ss == 'B' and Ts == 'B':
    lines[3].add((0,Si-1))
    lines[0].add((7,Ti-Si))
    lines[7].add((4,Y-Ti))
elif Ss == 'B':
    lines[3].add((0,Si-1))
    lines[0].add((4,Y-Si))
elif Ts == 'B':
    lines[3].add((7,Ti-1))
    lines[7].add((4,Y-Ti))

if Ss == 'C' and Ts == 'C':
    lines[5].add((0,Si-1))
    lines[0].add((7,Ti-Si))
    lines[7].add((6,Z-Ti))
elif Ss == 'C':
    lines[5].add((0,Si-1))
    lines[0].add((6,Z-Si))
elif Ts == 'C':
    lines[5].add((7,Ti-1))
    lines[7].add((6,Z-Ti))

lines[1].add((3,1))
lines[3].add((5,1))
lines[5].add((1,1))

lines[2].add((4,1))
lines[4].add((6,1))
lines[6].add((2,1))

lines[1].add((2,X-1))
lines[3].add((4,Y-1))
lines[5].add((6,Z-1))

for s in range(8):
    for t,c in lines[s]:
        lines[t].add((s,c))

weight = dijkstra(lines,N,0)
print(weight[-1])
0