ABC325E - Our clients, please wait a moment

解法1：頂点を倍にする

考え方

フェネック「いま車に乗ってるのか電車に乗ってるのかで頂点を倍にして、1つのグラフで1回だけダイクストラをする解法もあるよ。ちょっと違うけどこういうイメージだねー」https://t.co/9aukUafvmP

— 競技プログラミングをするフレンズ (@kyopro_friends) October 21, 2023

回答例

• 頂点$1$〜$N$：社用車を使った世界の頂点
• 頂点$N+1$〜$2N$：電車を使った世界の頂点

として，適切に辺を貼る．あとはダイクストラ．

from heapq import heapify, heappop, heappush

N, A, B, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(N)]

G = [[] for _ in range(2*N)]
for i in range(N):
    for j in range(N):
        if i == j:continue
        G[i].append((j, D[i][j] * A))
        G[i].append((j+N, D[i][j]*B + C))
        G[i+N].append((j+N, D[i][j]*B + C))

dist = [1<<60] * (2*N)
dist[0] = 0
q = [(0, 0)]
while q:
    d, cur = heappop(q)
    if dist[cur] < d:continue
    for chi, c in G[cur]:
        if d + c < dist[chi]:
            dist[chi] = d + c
            heappush(q, (d+c, chi))

print(min(dist[N-1], dist[2*N-1]))