개발조아

문제 링크 : 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 처음 풀이가 맞았는데 오타 때문에 지우고 다시 풀다가 오타를 발견하고 원래코드로 돌아와 푼 바보같은 문제였다. 하지만 결국 시간초과랑 싸운 문제이다. 알고리즘은 간단하다. 우선 최단경로를 구해야하므로 다익스트라를 사용했다. 그리고 각 노드를 방문했을 때의 상태가 달라야한다. 상태는 도로를 포장한 개수이다. 다음 도로를 포장하고 갈지 아니면 그냥 갈..