Koala - 10기/코딩테스트 준비 스터디
[백준/Python] 23033 : 집에 빨리 가고 싶어!
허수민
2023. 5. 20. 23:03
23033번: 집에 빨리 가고 싶어! (acmicpc.net)
23033번: 집에 빨리 가고 싶어!
첫째 줄에 역의 수 N(2 ≤ N ≤ 20,000)과 노선 M개(1 ≤ M ≤ 300,000)가 주어진다. 둘째 줄 부터 M개의 줄에 걸쳐서 4개의 정수 A, B, T, W가 주어지고 A역에서 B역으로 가는 단방향 노선이 존재하며, 소요
www.acmicpc.net
코드
해석
- 역의 수 N, 노선 M을 입력 받음
- a,b,t,w를 입력 받고 graph의 a행에 (b, t, w) 저장
- 시작 역부터 해당 역까지의 최소 시간을 저장하는 dist 리스트 생성
- 생성 직후 출발역에서는 0, 이외의 역에서는 INF(무한)
- 최소 시간이 작은 역부터 처리하기 위해 우선순위 큐인 q 사용
- 생성 직후 출발역인 0에서는 [0,1] push
- while문을 실행해 우선순위 큐인 q가 공백이 아니라면 계속 반복
- q에서 pop을 실행해 t와 now를 꺼내 해당 역으로의 최소 시간 갱신
- now가 최종 목적지인 마지막 역에 도착하면 현재까지의 시간 출력 후 종료