結果

問題 No.859 路線A、路線B、路線C
ユーザー ntuda
提出日時 2025-02-20 23:12:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 40 ms / 1,000 ms
コード長 956 bytes
コンパイル時間 2,632 ms
コンパイル使用メモリ 81,476 KB
実行使用メモリ 54,220 KB
最終ジャッジ日時 2025-02-20 23:12:59
合計ジャッジ時間 2,492 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

XYZ = list(map(int,input().split()))
ST = []
dic = {"A":0,"B":1,"C":2}
for i in range(2):
    s,t = input().split()
    t = int(t) - 1
    ST.append((s,t))

UV = [(0,1,1),(0,2,1),(1,2,1),(3,4,1),(4,5,1),(3,5,1),
      (0,3,XYZ[0]-1),(1,4,XYZ[1]-1),(2,5,XYZ[2]-1)]

if ST[0][0] == ST[1][0]:
    s, t1 = ST[0]
    t2 = ST[1][1]
    if t1 > t2:
        t1,t2 = t2,t1
    s = dic[s]
    UV.append((s,6,t1))
    UV.append((s + 3,7,XYZ[s] - t2 - 1))
    UV.append((6,7,abs(t1-t2)))
else:
    s, t = ST[0]
    s = dic[s]
    UV.append((s,6,t))
    UV.append((s + 3,6,XYZ[s] - t - 1))
    s, t = ST[1]
    s = dic[s]
    UV.append((s,7,t))
    UV.append((s + 3,7,XYZ[s] - t - 1))

E = [[] for _ in range(8)]
for u, v, c in UV:
    E[u].append((v,c))
    E[v].append((u,c))
INF = 10 ** 10
dp = [INF] * 8
dp[6] = 0
Q = [6]
while Q:
    x = Q.pop()
    for y,t in E[x]:
        if dp[y] > dp[x] + t:
            dp[y] = dp[x] + t
            Q.append(y)
print(dp[7])
0