[백준/BOJ] 백준 1162번 : 도로포장

www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하 www.acmicpc.net 포장할 수 있는 도로의 개수를 스킵할 수 있는 도로의 개수라고 생각을 했다. 다익스트라를 이용해서 문제를 해결하였는데, result[위치][앞으로 포장할 수 있는 도로] = 최소 시간을 저장하였고, pq에 (-비용,(위치,앞으로 포장할 수 있는 도로))를 저장하였다. 그리고 다익스트라를 진행하며 포장할 수 있는 도로의 개수가 있을 때는 현재 here-there 도로 포장 하는..

2021.02.08