AtCoder Beginner Contest 214 C - Distributionの勉強

atcoder.jp

・参考：
　DPのやり方はDistribution [AtCoder Beginner Contest 214 C] - はまやんはまやんはまやん
　ダイスクラ法はEditorial - AtCoder Beginner Contest 214を参考にした。

・説明：
　この問題は2つやり方があり、DPとダイスクラ法でできる。
　注意点として、DPでは円上なので例えばN=4のとき4,3,2,1が最適解の場合もあるので2周する必要がある。
　詳しい説明はコメントアウトしている。

・DP

n=int(input())
s=list(map(int,input().split()))
t=list(map(int,input().split()))

dp=[10**18 for _ in range(n)]
dp[0]=t[0]

#2周する理由は例えばn=4のとき、3, 4, 1, 2となる場合もあるので。
for i in range(n*2):
  dp[(i+1)%n]=min(dp[i%n]+s[i%n],t[(i+1)%n])   #i=n-1のとき(i+1)%n=0となりdp[0]が更新され2周目が始まる。
  
for i in range(n):
  print(dp[i])

・ダイスクラ法

from collections import deque
n=int(input())
s=list(map(int,input().split()))
t=list(map(int,input().split()))

g=[[]for _ in range(n+1)]
#高橋さんから行ける頂点(i+1)とその返の重さ(t[i])をg[0]に追加。
for i in range(n):
  g[0].append((i+1, t[i]))
  
#頂点1，2，3，、、から行ける頂点とその重さ。
for i in range(1,n+1):
  #最後の頂点だけ1に行くから。
  if i==n:
    g[i].append((1, s[-1]))
  else:
    g[i].append((i+1, s[i-1]))

dist=[10**18 for _ in range(n+1)]
dist[0]=0  #dist[0]が高橋さん。

que=deque()
que.append(0)

#ダイスクラ法
while len(que)!=0:
  v=que.popleft()
  for nv, w in g[v]:
    d=dist[v]+w
    if d<dist[nv]:
      dist[nv]=d
      que.append(nv)

for i in range(n):
  print(dist[i+1])