문제 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 풀이 solved.ac 난이도: Gold 1 다이나믹 프로그래밍을 적용하여 해결하는 다익스트라 문제. 단순히 모든 도로들 중 K개의 도로들을 선택하여 cost를 0으로 만든다면, 모든 조합의 최대 수는 Combination(50000 , 20) 일 것이다. 이는 절대 시간안에 계산해낼 수 있는 수치가 아니다. 따라서 다익스트라를 진행하면서 방문하게 되는 간..