[graph] [힙큐] 15704번: 백준 마라톤 대회

 

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

15704번: 백준 마라톤 대회

import heapq

MAX = 100000
INF = float('inf')

def InputData():
    N, M, K = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        u, v, c, t = map(int, input().split())
        u -= 1
        v -= 1
        G[u].append((v, c, t))
        G[v].append((u, c, t))
    return N, M, K, G

def main():
    N, M, K, G = InputData()
    
    lo, hi = 1, int(1e9)
    while lo <= hi:
        mid = (lo + hi) // 2

        dist = [INF] * N
        visited = [False] * N
        dist[0] = 0
        queue = []
        heapq.heappush(queue, (0, 0))
        while queue:
            cur_cost, cur = heapq.heappop(queue)
            if visited[cur] or dist[cur] > K:
                break
            visited[cur] = True

            for next_node, c, t in G[cur]:
                if mid > t and (c * ((mid - t) * (mid - t))) > K:
                    continue
                
                price = c * (mid - t) * (mid - t) if mid > t else 0
                if dist[cur] + price < dist[next_node]:
                    dist[next_node] = dist[cur] + price
                    heapq.heappush(queue, (dist[next_node], next_node))

            heapq.heapify(queue)

        if dist[N-1] <= K:
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

print(main())