[BOJ 23033, Python 3] 집에 빨리 가고 싶어!

https://www.acmicpc.net/problem/23033

23033번: 집에 빨리 가고 싶어!

 

 

풀이

최단 시간을 구해야 하는데, A역에서 B역으로 가는데 걸리는 시간이 T이므로 다익스트라 알고리즘을 생각해볼 수 있습니다.

그리고 새로운 열차를 기다려서 타는 방법은 현재 시간이 W의 배수이면 그대로 현재 시간을 우선순위 큐에 넣어주고, 현재 시간이 W의 배수가 아니라면 (W - (현재 시간) % W)만큼 시간을 추가하여 움직이게 해주면 됩니다.

 

 

코드

input = __import__('sys').stdin.readline
from heapq import *
 
n, m = map(int, input().split())
adj = [[] for _ in range(n+1)]
for i in range(m):
    a, b, t, w = map(int, input().split())
    adj[a].append((b, t, w))
q = []; heappush(q, [0, 1])
S = [float('inf')] * (n + 1); S[1] = 0
while q:
    t, x = heappop(q)
    if S[x] != t: continue
    if x == n: print(t); exit()
    for nx, nt, w in adj[x]:
        val = t + nt + (0 if t % w == 0 else w - (t % w))
        if S[nx] > val:
            S[nx] = val
            heappush(q, [val, nx])