[백준] 1162 도로포장

 

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

1162번: 도로포장

1번에서 N번까지 가능 경우의 수를 구하라 => 다익스트라

하지만, K개의 도로를 포장할 수가 있습니다.

각 노드에서 할 수 있는 일

각 노드에서 도로를 포장해서 갈지 아니면 그냥 갈지 2가지의 경우가 존재합니다.

2가지의 모든 경우를 dis[n][k]에 다 담을 수 있고

dis[n][k]가 작아질때만 q에 추가해 역으로 다시 돌아갈 일이 존재하지 않기때문에 DP를 적용시킬 수 있습니다.

 

import sys

input = sys.stdin.readline

N, M, K = map(int, input().split())
l = [[] for i in range(N + 1)]
for i in range(M):
    a, b, c = map(int, input().split())
    l[a].append([b, c])
    l[b].append([a, c])
q = [[0, 1, 0]]
dis = [[float('inf')] * (K + 1) for i in range(N + 1)]
import heapq

hpush = heapq.heappush
hpop = heapq.heappop
dis[1][0] = 0
while q:
    d, now, k = hpop(q)
    if dis[now][k] < d:
        continue
    for to, d in l[now]:
        if k < K and dis[to][k + 1] > dis[now][k]:
            dis[to][k + 1] = dis[now][k]
            hpush(q, [dis[to][k + 1], to, k + 1])
        if dis[to][k] > dis[now][k] + d:
            dis[to][k] = dis[now][k] + d
            hpush(q, [dis[to][k], to, k])
# print(dis)
# print(dis[-1][K])
print(min(dis[-1]))

여기서 마지막 줄을 주석 처럼 쓸 경우

4 3 2
1 4 5
1 3 100
3 2 5

일 경우 dis[-1]가 처럼 됩니다.

[inf, inf, inf]
[0, 5, 0]
[105, 5, 0]
[100, 0, 5]
[5, 0, 5]

1 -> 3 -> 1 - > 4로 갈 경우 도로 2개를 지워 5만으로 4로 갈 수 있습니다.

따라서 도로를 1개만 지워 1 -> 4로 가는게 가장 빠르므로 주의를 해줘야 합니다.