1. 문제 설명

지각하면 안 돼

2. 문제 분석

비용/시간을 모두 비교 기준으로 삼고 다익스트라 알고리즘을 사용해야 한다. distances를 이차원 배열로 파악하고 일차적으로는 비용, 이차적으로는 시간에 따른 이득이 있을 때 값을 갱신한다. 제한 시간 및 제한 비용에 따라 필터링하기 때문에 이차원 배열에 기록되는 모든 값은 사용 가능한 값이고, 이중 최소 비용을 리턴한다.

3. 나의 풀이

import sys
import heapq

INF = sys.maxsize

def Dijkstra():
    distances = [[INF for _ in range(t+1)] for _ in range(n+1)]
    distances[1][0] = 0
    pq = []
    heapq.heappush(pq, [0, 0, 1])

    while pq:
        cur_cost, cur_time, cur_node = heapq.heappop(pq)
        if distances[cur_node][cur_time] < cur_cost: continue

        for next_node, next_time, next_cost in nodes[cur_node]:
            if t < next_time + cur_time or m < next_cost + cur_cost: continue
            if distances[next_node][next_time+cur_time] > next_cost + cur_cost:
                distances[next_node][next_time+cur_time] = next_cost + cur_cost
                heapq.heappush(pq, [next_cost+cur_cost, next_time+cur_time, next_node])
    answer = min(distances[n])
    if answer == INF: return -1
    else: return answer

n = int(sys.stdin.readline().rstrip())
nodes = [[] for _ in range(n+1)]
t, m = map(int, sys.stdin.readline().rstrip().split())
l = int(sys.stdin.readline().rstrip())
for _ in range(l):
    a, b, c, d = map(int, sys.stdin.readline().rstrip().split())
    nodes[a].append([b, c, d])
    nodes[b].append([a, c, d])
print(Dijkstra())