https://www.acmicpc.net/problem/1162문제조건 N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장포장하게 되면 도로를 지나는데 걸리는 시간이 0서울은 1번 도시, 포천은 N번 도시 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간은?접근방법 가중치가 있는 그래프에서 특정지점에서 시작해서 다른지점까지의 최단거리를 구하는 알고리즘인 다익스트라가 떠올랐다. 사실 이 문제는 푸는것 자체는 크게 어렵지 않았다. 다익스트라 알고리즘 자체가 dp를 기반으로 이때까지 계산된 거리와 새로운 거리를 비교해서 계속해서 기록하는 구조이므로, 엄청나게 큰값이 들어 갈수 있기때문엥 21억이 넘는 수 까지 처리해..