ABC342 E - Last Train

atcoder.jp

問題

• N個の駅があるよ！
• 電車の情報がM個与えられるよ！
  • 駅Aから駅Bまで、cの時間がかかるよ！
  • l,l+d,l+2d,...,l+(k-1)dの時刻に駅Aから列車が発車するよ！
• 以下の一覧を求めてね！
  • 駅1から駅Nに到着できる最終時刻
  • 駅2から駅Nに到着できる最終時刻
  • 駅3から駅Nに到着できる最終時刻…
  • 駅N-1から駅Nに到着できる最終時刻

成約

• $2 \leq N \leq 2 \times 10^{5}$
• $1 \leq M \leq 2 \times 10^{5}$

思考

• 駅がN個、線路がM本…それぞれの線路の長さ(c)が、あるので、ダイクストラを疑う
• 辺がM本なら、簡単にダイクストラで…地点Nからの最短距離が求められるよね
  • 今回は最終時刻がほしいので、プラスマイナス気をつけなきゃね
• 問題は、辺の上限がとても多いので…$10^{14}$本とか貼るのは流石にえげつない…
  • M本の路線それぞれに応じて、乗るべき最終電車が一本決まるからこれをどうにか見つけたいね！
  • rangeにbisectが使える！すごい！
    • $10^{9}$の配列を作らなくても、等差数列の二分探索ができる！すごい！
  • 計算一発系でもいけそうだけど、上手く纏めるの難しい…

コード

from bisect import bisect_right
from heapq import heappush, heappop

N,M = map(int,input().split())
edge_L = [[] for _ in range(N)]
for _ in range(M):
    l,d,k,c,A,B = map(int,input().split())
    A-=1
    B-=1
    edge_L[B].append((range(l,l+k*d,d),c,A)) # rangeオブジェクトで辺の情報を取得

time_limit = [-float('inf')]*N
time_limit[-1] = float('inf')

hq = []
hq.append((-float('inf'),N-1))

while hq:
    time,now_node = heappop(hq)
    time = -time

    if time_limit[now_node] > time:continue

    for r,c,next_node in edge_L[now_node]:
        idx = bisect_right(r,time-c)
        if idx == 0:continue

        next_time = r[idx-1]

        if time_limit[next_node] >= next_time:continue
        time_limit[next_node] = next_time
        heappush(hq,(-time_limit[next_node],next_node))

for time in time_limit[:-1]:
    if time == -float('inf'):
        print("Unreachable")
    else:
        print(time)