kthng

codeground : 대피소 [SCPC 2016 - 1차 예선] https://www.codeground.org/practice/practiceProbView.do?probId=28 떠올릴 수 있는 가장 간단한 방법은 v번의 다익스트라를 하는 것. 하지만 이 방법은 간단히 시간초과임을 알 수 있다. 그렇다면 다른 해결방법이 있을까? 이 문제는 단 한번의 다익스트라로 해결이 가능하다.heap에 모든 대피소를 넣고 시작하면 된다. 또한, 경로의 길이가 같을 경우 대피소번호가 작은 대피소를 선택하는 것도 동시에 해결해주면 된다. 알고리즘을 간략히 써보면, 1. 새로운 경로가 더 작으면 힙에 push. dist 갱신 위에께 일반적인 다익스트라 알고리즘이라면, 이문제에 해당하는 알고리즘은 다음과 같다. 1. 새..