ABC164 E Two Currencies

内容

ABC164 のE問題(500点) Two Currenciesを、python出といた。

問題

atcoder.jp

考えたこと

• 各頂点への最短時間なので、dijkstraしたい。
• 移動できるかどうかは所持金に関わってくる。
  • 所持金も状態として持ちたい。

ポイント

• u->vの移動にかかる金額は高々50程度

• 任意の頂点までは、N-1回以内の移動でたどり着くことができる。

• 所持金のオーダーは10**9

• 全部の移動に50かかって、N-1距離でも、50(N-1)の金額しか必要ない。

  実装

from collections import defaultdict
import heapq

N,M,S = map(int,input().split())
Edges=[list(map(int,input().split())) for _ in range(M)]
Exchanges=[list(map(int,input().split())) for _ in range(N)]

max_money=max([a for _,_,a,_ in Edges])*N

Graph=defaultdict(lambda :[])

#nodeと状態は tupleで管理する。(node,money)
#Graph[cur_state]=[ (cost,next_state),...]


for u,v,a,b in Edges:
    u-=1;v-=1
    for cur_money in range(max_money+1):
        if cur_money-a<0:#お金が足りなくて移動できない
            continue
        from_state_u=(u,cur_money)
        to_state_v=(v,cur_money-a)
        Graph[from_state_u].append((b,to_state_v))

        from_state_v=(v,cur_money)
        to_state_u=(u,cur_money-a)
        Graph[from_state_v].append((b,to_state_u))

for n,[c,d] in enumerate(Exchanges):
    for cur_money in range(max_money+1):
        after_money=min(max_money,cur_money+c)#両替後のお金(money_max以上は同じにする)
        from_state=(n,cur_money)
        to_state=(n,after_money)
        Graph[from_state].append((d,to_state))



# Dijksttra する
#startの状態(Sがmax_moneyより大きいならmax_moneyにする)
start=(0,min(max_money,S))

Q=[(0,start)]

dist=defaultdict(lambda :float('inf'))
dist[start]=0

while Q:
    q = heapq.heappop(Q)
    cur_time,cur_state=q

    if dist[cur_state]<cur_time:
        continue
    for cost,next_state in Graph[cur_state]:
        next_time = cost+cur_time

        if dist[next_state]>next_time:
            dist[next_state]=next_time
            heapq.heappush(Q,(next_time,next_state))

for dest in range(1,N):
    ans=float("inf")
    #goal次の所持金は関係ないので、ある頂点のあらゆる所持金に対してminをとる
    for a in range(max_money+1):
        state=(dest,a)
        ans=min(ans,dist[state])
    print(ans)

終わりに