BOJ 1162 도로포장

https://www.acmicpc.net/problem/1162
시간 2초, 메모리 128MB

input :

• N M K(1 ≤ N ≤ 200,000)(1 ≤ M ≤ 50,000)(1 ≤ K ≤ 20)
• 도시 도시 시간 (양방향 도로, 1 <= 시간 <= 1,000,000)

output :

• K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력

조건 :

• 도로는 이미 있는 도로만 포장

• 포장하게 되면 도로를 지나는데 걸리는 시간이 0

• 1번에서 N번까지 항상 갈 수 있는 데이터만 주어진다.

---

가장 중요한 부분은 어떤 도로를 포장할 것인가 이다.

1. 모든 경우의 수 해보기
   당연히 터질 거다. 50000개 중 20개를 고르는 조합의 경우의 수면.. 상상하기 싫다.

2. 기록
   결국 다 기록해야 하는 거였다. 이전 까지 포장한 도로 개수를 가지고 현재 도로를 포장할지 말지를 생각하는 거다.

생각의 과정을 다음에는 이렇게 하도록 하자.
특정 도로로 이동을 해야 하는데 갈 수 있는 방법이 무엇이 있는가? 그냥 가거나 해당 도로를 포장하는 것.
그러면 이걸 어떻게 기록 할까? q에다가 넣을 때 현재 방법으로 몇 번 더 포장할 수 있는지를 생각하자.

이 부분을 생각한다면 남은 부분은 다익스트라를 사용하면 된다.
기본 코드에서와 같이 while문 아래에 조건문을 달아서 현재 cost가 저장한 최단 거리보다 클 때에만 확인을 하지 않는다.
이 부분이 visit 부분을 대신 한다.

주의.
1. 양방향
2. dp의 시작 노드에 해당하는 부분 모두 초기화
3. 거리가 업데이트 되면 q에 추가하기

import sys
from heapq import heappop, heappush

n, m, k = map(int, sys.stdin.readline().split())
graph, distance = [[] for _ in range(n + 1)], [[float('inf')] * (k + 1) for _ in range(n + 1)]

for i in range(k + 1):
    distance[1][i] = 0

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((c, b))
    graph[b].append((c, a))

q = []
heappush(q, (0, k, 1))
while q:
    cost, cnt, node = heappop(q)

    if cost > distance[node][cnt]:
        continue

    for next_cost, next_node in graph[node]:
        if cnt >= 1 and cost < distance[next_node][cnt - 1]:
            distance[next_node][cnt - 1] = cost
            heappush(q, (cost, cnt - 1, next_node))

        if cost + next_cost < distance[next_node][cnt]:
            distance[next_node][cnt] = min(distance[next_node][cnt], cost + next_cost)
            heappush(q, (cost + next_cost, cnt, next_node))

print(min(distance[n]))