[Python/BOJ] 12763. 지각하면 안 돼

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

12763번: 지각하면 안 돼

문제

준하는 평범한 대학생이다. 이번 학기는 수강신청에 완전히 실패했다. 그러다 보니 수업시간표가 엉망이라 수업마다 옮겨 다닐 건물이 많다.

이런 건물들에는 모두 이름이 있지만, 매번 건물의 이름까지 모두 적기엔 잉크가 아까웠다. 그래서 편의상, 옮겨다닐 건물이 \(N\)개가 있다면 1호관 ~ \(N\)호관이라 부르기로 했다.

이렇듯 건물이 많다 보니 지각을 하는 경우가 빈번했는데, 1호관에 있는 준하는 \(N\)호관에서 듣는 이번 수업에 출석하지 못하면 F 학점을 받을 위기에 놓여있다.

준하는 지각을 면하기 위해 택시를 자주 타곤 했는데, 각 건물들 간에 이동하는 데 걸리는 시간과 택시비를 노트에 메모해두었다. 노트가 몇 장 없기때문에 이미 적어놨던 길은 다시 적지 않았다. 건물 사이에는 길이 하나밖에 없어서 노트에 이미 적은 것과 다른 시간이나 다른 택시비인 경우는 한차례도 없었다. 가는 길과 오는 길 역시 모두 같았다.

학사경고가 걸린 긴박한 상황이기 때문에, 노트에 적히지 않은 새로운 길을 간다거나 하는 모험은 피하기로 했다.

아래는 건물이 5개가 있는 경우이다.

그동안의 메모를 이용해 지금 1호관에서 듣는 수업이 끝나고 3시간 안에 5호관까지 가야 한다. 급하게 노트에 펼쳐봤지만, 어떻게 가야 하는 지 도저히 모르겠다.

가진 돈이라고는 4,000원밖에 없는 준하는 3시간 이내에 5호관까지 가야 하는 데, 이번 달은 남은 돈으로 살아가야 하기 때문에 가진 돈의 지출을 최소화하고 싶다.

이런 일이 앞으로도 자주 있을 것이기 때문에, 이번 수업은 포기하고 다음을 위해 일반화된 프로그램을 당신에게 간곡히 부탁했다.

건물과 건물 사이에 이동하는 데 걸리는 시간과 택시비, 현재 가지고 있는 돈을 알고 있을 때, \(T\)분 내에 얼마의 최소 지출로 도착할 수 있는지 출력하는 프로그램을 만들어주자.

입력

첫째 줄에 건물의 개수 \(N (2 \le N \le 100) \)이 주어진다.

둘째 줄에 수업 출석까지 남은 시간 \(T (1 \le T \le 10,000) \)(분) 과 현재 가지고 있는 돈 \(M (0 \le M \le 10,000) \)이 차례로 주어진다.

셋째 줄에 노트에 적혀있는 건물 사이의 길의 개수 \(L(1 ≤ L \le10,000)\)이 주어진다.

다음 \(L\)개의 줄에 걸쳐 길의 양 끝에 있는 두 건물의 번호와 이동 시간(분), 택시비가 주어진다. 이동시간과 택시비는 모두 10,000을 넘지 않는 자연수이다. 양 끝에 있는 두 건물의 번호는 서로 다름이 보장된다.

출력

 \(T\)분 이내에 1번 건물에서 \(N\)번 건물까지 \(M\)만큼의 돈 이하로 갈 수 있다면, 최소 얼마의 지출이 예상되는지 출력한다.

만약 갈 수 없다면 -1을 출력한다.

풀이

Code

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

# 1. 다익스트라 함수 생성
def dijkstra(start) :
    # 1-1. 힙 생성 후 (0, 0, 1) 삽입
    heap = []
    heappush(heap, (0, 0, 1))
    # 1-2, 현재 노드 정보 업데이트
    information[1] = [0, 0]
    # 1-3.
    while heap :
        # 1-3-1. 힙에서 정보 반환
        now_m, now_t, node = heappop(heap)
        # 1-3-2. 이미 처리가 된 경우 continue
        if information[node][0] < now_m and information[node][1] < now_t : continue
        # 1-3-3.
        for next, time, cost in graph[node] :
            # 돈, 시간 계산
            next_m, next_t = now_m + cost, now_t + time
            # 돈 또는 시간이 초과할 경우 continue
            if next_m > m or next_t > t : continue
            # 시간이 절약될 경우 정보 업데이트
            if next_m < information[next][0] or (next_m == information[next][0] and next_t < information[next][1]): information[next] = [next_m, next_t]
            # 힙에 정보 삽입
            heappush(heap, (next_m, next_t, next))

n = int(input())
t, m = map(int, input().split())
l = int(input())

# 2. 그래프 생성 후 업데이트
graph = [[] for _ in range(n+1)]
for _ in range(l) :
    a, b, time, cost = map(int, input().split())
    graph[a].append((b, time, cost))
    graph[b].append((a, time, cost))
# 3. 시간-돈 정보 리스트 생성
INF = float("inf")
information = [[INF, INF] for _ in range(n+1)]
# 4. 다익스트라 실행
dijkstra(1)
# 5. 결과 출력
print(information[-1][0] if information[-1][0] != INF else -1)