ABC164 E - Two Currencies - あっとのTECH LOG

問題原文

問題要旨

金貨めっちゃたくさんと銀貨 $S$ 枚を持って、 $N$ 頂点 $M$ 辺の無向連結グラフを頂点０から旅することを考える。
各辺には通行料が設定されており、銀貨 $A_i$ 枚を払わないと通れず、移動に $B_i$ 分かかる。
また、各頂点には両替所が設定されており、金貨１枚を銀貨 $C_i$ 枚に、 $D_i$ 分で両替することができる。
頂点０から各頂点にたどり着くまでの最短時間を求めよ。

$1 \leq N \leq 50$
$N - 1 \leq M \leq 100$
$0 \leq S \leq 10^{9}$
$1 \leq A \leq 2500$
$1 \leq B_i, C_i, D_i \leq 10^{9}$
二重辺、自己ループなし

解法

$A_i$ の制約が小さいので、銀貨は最大でも2500枚ぐらいあれば十分なことがわかる。これで $S$ のデカ制約を無視できる。
状態の同一視がカギで、
$dp[i\rbrack[silver\rbrack :=$ 頂点 $i$ にいて銀貨を $silvver$ 枚持っているような状態になるための最短時間
として拡張ダイクストラで解けばいい。

実装

頂点 $i$ に留まって両替だけする場合、を別でわけて書いたら見通しがよくなりそう。

import heapq
N, M, init_silver = map(int, input().split())
MAX_COST = 2500
init_silver = min(init_silver, MAX_COST)

G = [[] for _ in range(N)]
for i in range(M):
    u, v, silver_cost, time_cost = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append([v, silver_cost, time_cost])
    G[v].append([u, silver_cost, time_cost])

change_rate, change_cost = [], []
for i in range(N):
    rate, cost = map(int, input().split())
    change_rate.append(rate)
    change_cost.append(cost)

# dp[i][silver] := 頂点iにいて銀貨をsilver枚持っているような状況を作るために必要な最小時間
dp = [[float('inf')] * (MAX_COST + 1) for _ in range(N)]
dp[0][init_silver] = 0

# 優先度付きキュー: (time, node, silver)
hq = [(0, 0, init_silver)]
while hq:
    time, node, silver = heapq.heappop(hq)

    self_loop_silver = min(silver + change_rate[node], MAX_COST)
    self_loop_cost = time + change_cost[node]
    if self_loop_cost < dp[node][self_loop_silver]:
        dp[node][self_loop_silver] = self_loop_cost
        heapq.heappush(hq, (time + change_cost[node], node, self_loop_silver))

    for to, silver_cost, time_cost in G[node]:
        remain_silver = min(silver - silver_cost, MAX_COST)
        if remain_silver < 0:
            continue

        dp_next_value = time + time_cost
        if dp[to][remain_silver] <= dp_next_value:
            continue

        dp[to][remain_silver] = dp_next_value
        heapq.heappush(hq, (dp_next_value, to, remain_silver))

print(*[min(d) for d in dp[1:]], sep="\n")

銀貨コストを $-C_i$ にして、時間コストを $D_i$ 、移動先を自身とするような自己ループを各頂点に追加してもできる。
こっちのがダイクストラ部分の見通しがよい、けどちょっとだけ思考レベルが高そう。（しらんけど）

import heapq
N, M, init_silver = map(int, input().split())
MAX_COST = 2500
init_silver = min(init_silver, MAX_COST)

G = [[] for _ in range(N)]
for i in range(M):
    u, v, silver_cost, time_cost = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append([v, silver_cost, time_cost])
    G[v].append([u, silver_cost, time_cost])

change_rate, change_cost = [], []
for i in range(N):
    rate, cost = map(int, input().split())
    G[i].append([i, -rate, cost])  # これを追加！
    change_rate.append(rate)
    change_cost.append(cost)


# dp[i][silver] := 頂点iにいて銀貨をsilver枚持っているような状況を作るために必要な最小時間
dp = [[float('inf')] * (MAX_COST + 1) for _ in range(N)]
dp[0][init_silver] = 0

# 優先度付きキュー: (time, node, silver)
hq = [(0, 0, init_silver)]
while hq:
    time, node, silver = heapq.heappop(hq)

    for to, silver_cost, time_cost in G[node]:
        remain_silver = min(silver - silver_cost, MAX_COST)
        if remain_silver < 0:
            continue

        dp_next_value = time + time_cost
        if dp[to][remain_silver] <= dp_next_value:
            continue

        dp[to][remain_silver] = dp_next_value
        heapq.heappush(hq, (dp_next_value, to, remain_silver))

print(*[min(d) for d in dp[1:]], sep="\n")

感想

本番なんか無限にバグらせたけど、今見たらサクッと解けてやるせない気持ちになった。
落ち着こう、ね。