1162. 도로포장

업데이트 시간 : 2023-04-11 06:01:50 +0000

[Gold I] 도로포장 - 1162

성능 요약

메모리: 56132 KB, 시간: 2800 ms

분류

다이나믹 프로그래밍, 그래프 이론, 데이크스트라

문제 설명

준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 K개의 도로를 포장하여 서울에서 포천까지 가는 시간을 단축하려 한다.

문제는 N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 도로는 이미 있는 도로만 포장할 수 있고, 포장하게 되면 도로를 지나는데 걸리는 시간이 0이 된다. 또한 편의상 서울은 1번 도시, 포천은 N번 도시라 하고 1번에서 N번까지 항상 갈 수 있는 데이터만 주어진다.

입력

첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하는데 걸리는 시간이 주어진다. 도로들은 양방향 도로이며, 걸리는 시간은 1,000,000보다 작거나 같은 자연수이다.

출력

첫 줄에 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력한다.

💡 Solutions

📄 도로포장.py

import sys
import heapq

N, M, K = map(int, sys.stdin.readline().split())

def dijkstra(start):
    heap = []
    heapq.heappush(heap, (0, start, 0)) # distance, start, 포장
    

    while heap:
        check, now, poz = heapq.heappop(heap)

        if d[now][poz] < check:
            continue
        
        if poz + 1 <= K:
            for v, w in adj[now]:
                if d[v][poz+1] > check:
                    d[v][poz+1] = check
                    heapq.heappush(heap, (check, v, poz+1))

        for v, w in adj[now]:
            tmp = w + check
            if d[v][poz] > tmp:
                d[v][poz] = tmp
                heapq.heappush(heap, (tmp, v, poz))

adj = [tuple() for _ in range(N+1)]
for _ in range(M):
    s, e, w = map(int, sys.stdin.readline().split())
    adj[s] += ((e, w),)
    adj[e] += ((s, w),)



d = [[1000000*10000] * (K+1) for _ in range(N+1)]


for i in range(K + 1):
    d[1][i] = 0

ans = 1000000*10000
dijkstra(1)
for i in range(K + 1):
    ans = min(ans, d[N][i])
print(ans)