[백준/python] 23033 집에 빨리 가고 싶어!

import sys
from math import ceil
from heapq import heappop, heappush

input = sys.stdin.readline

def dijkstra():
    while hq:
        time_now, now = heappop(hq)
        if time_now > distance[now] : continue
        for nxt, cost, schedule in graph[now]:
            time_nxt = cost + ceil(time_now/schedule)*schedule  # 현재 시간 (time_now 가 schedule의 배수와 맞춰져야함) 
            if distance[nxt] > time_nxt:
                distance[nxt] = time_nxt
                heappush(hq, (time_nxt, nxt))

N,M = map(int,input().split())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    A,B,T,W = map(int,input().split())
    graph[A].append((B,T,W))

distance = [float("inf")] * (N+1)
distance[1] = 0

hq = [(0,1)]
dijkstra()
print(distance[N])

다익스트라 알고리즘

이 문제는 1번 노드에서 N번 노드까지 갈 때의 최단 거리를 구하는 문제로, 다익스트라 알고리즘을 활용해야 합니다.

heapq자료구조와 distance 배열을 활용하여 다익스트라 함수를 만들고, 문제에서 요구하는 각 열차의 운행시간을 맞추기 위해 time_nxt를 구할 때 현재 시간에서 가장 가까운 운행 주기를 찾고, 소요 시간을 더해 계산합니다.

그 외에는 일반적인 다익스트라와 다른 점이 없는 문제입니다.