結果

問題 No.859 路線A、路線B、路線C
ユーザー simamumusimamumu
提出日時 2019-08-09 21:57:40
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 35 ms / 1,000 ms
コード長 1,915 bytes
コンパイル時間 101 ms
コンパイル使用メモリ 11,372 KB
実行使用メモリ 10,380 KB
最終ジャッジ日時 2023-09-26 17:51:35
合計ジャッジ時間 1,643 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
10,220 KB
testcase_01 AC 32 ms
10,328 KB
testcase_02 AC 33 ms
10,228 KB
testcase_03 AC 34 ms
10,260 KB
testcase_04 AC 33 ms
10,188 KB
testcase_05 AC 33 ms
10,380 KB
testcase_06 AC 32 ms
10,256 KB
testcase_07 AC 33 ms
10,324 KB
testcase_08 AC 33 ms
10,256 KB
testcase_09 AC 32 ms
10,220 KB
testcase_10 AC 32 ms
10,256 KB
testcase_11 AC 34 ms
10,228 KB
testcase_12 AC 33 ms
10,216 KB
testcase_13 AC 33 ms
10,260 KB
testcase_14 AC 33 ms
10,172 KB
権限があれば一括ダウンロードができます

ソースコード

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