[백준] 1162번 도로포장 파이썬

문제

준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 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개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력한다.

예제 입력 1

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

예제 출력 1

1

제출 답안

• 핵심은 도로 포장 횟수마다 거리의 값 변화다.
• 도로 포장하지 않은 거리와 도로 포장한 거리를 계속 변화해주면 된다.
  • 도로를 포장하면 거리가 더 짧아진다면 도로를 포장한다.
  • 도로 포장한 횟수의 거리를 업데이트 한다.
• 포장횟수 0번일때 거리, 1번일때 거리를 계속해서 k번까지 업데이트 하면 된다.

'''
1. 아이디어
- N까지 가는 길에 가장 최댓값 찾고
- k개만 포장
2. 시간복잡도
- O(ElogN)
- logN = log10000 = ~= 13
- E = 50,000
- 650,000 <2억
3. 변수
edge []
dist []
'''

import sys
import heapq
input = sys.stdin.readline
INF = sys.maxsize
n, m, k = map(int, input().split())

edge = [[] for _ in range(n+1)]
dist = [[INF] * (k+1) for _ in range(n+1)]

for _ in range(m):
    u, v, w = map(int, input().split())
    edge[u].append((w, v))
    edge[v].append((w, u))


dist[1][0] = 0
heap = [(0, 1, 0)]
while heap:
    cw, cv, cnt = heapq.heappop(heap)
    if dist[cv][cnt] < cw:continue
    for nw, nv in edge[cv]:
        nxt_w = cw + nw
        if dist[nv][cnt] > nxt_w:
            dist[nv][cnt] = nxt_w
            heapq.heappush(heap, (nxt_w, nv, cnt))

        if cnt < k and dist[nv][cnt+1] > cw:
            dist[nv][cnt +1] = cw
            heapq.heappush(heap, (cw, nv, cnt +1))

print(min(dist[n]))