https://www.acmicpc.net/problem/1162
1162번: 도로포장
첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하
www.acmicpc.net
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로 가는게 가장 빠르므로 주의를 해줘야 합니다.
'알고리즘 > 백준' 카테고리의 다른 글
[백준] K-지폐 28131 (1) | 2023.05.31 |
---|---|
[ BOJ 백준 1219 오민식의 고민] (0) | 2021.05.18 |
백준 16500번 문자열 판별 (0) | 2021.04.06 |
[ BOJ 백준 2104번 - 부분배열 고르기 ] (0) | 2021.04.01 |
[ BOJ 백준 1725번: 히스토그램 ] (0) | 2021.03.31 |