알고리즘/BOJ
[BOJ 23033, Python 3] 집에 빨리 가고 싶어!
70825
2021. 10. 5. 12:58
반응형
https://www.acmicpc.net/problem/23033
23033번: 집에 빨리 가고 싶어!
첫째 줄에 역의 수 N(2 ≤ N ≤ 20,000)과 노선 M개(1 ≤ M ≤ 300,000)가 주어진다. 둘째 줄 부터 M개의 줄에 걸쳐서 4개의 정수 A, B, T, W가 주어지고 A역에서 B역으로 가는 단방향 노선이 존재하며, 소요
www.acmicpc.net
풀이
최단 시간을 구해야 하는데, A역에서 B역으로 가는데 걸리는 시간이 T이므로 다익스트라 알고리즘을 생각해볼 수 있습니다.
그리고 새로운 열차를 기다려서 타는 방법은 현재 시간이 W의 배수이면 그대로 현재 시간을 우선순위 큐에 넣어주고, 현재 시간이 W의 배수가 아니라면 (W - (현재 시간) % W)만큼 시간을 추가하여 움직이게 해주면 됩니다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
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])
|
cs |
반응형