codeground : 대피소 [SCPC 2016 - 1차 예선]

codeground : 대피소 [SCPC 2016 - 1차 예선]

https://www.codeground.org/practice/practiceProbView.do?probId=28

떠올릴 수 있는 가장 간단한 방법은 v번의 다익스트라를 하는 것. 하지만 이 방법은 간단히 시간초과임을 알 수 있다.

그렇다면 다른 해결방법이 있을까?

이 문제는 단 한번의 다익스트라로 해결이 가능하다.

heap에 모든 대피소를 넣고 시작하면 된다.

또한, 경로의 길이가 같을 경우 대피소번호가 작은 대피소를 선택하는 것도 동시에 해결해주면 된다.

알고리즘을 간략히 써보면,

1. 새로운 경로가 더 작으면 힙에 push. dist 갱신

위에께 일반적인 다익스트라 알고리즘이라면, 이문제에 해당하는 알고리즘은 다음과 같다.

1. 새로운 경로가 더 작으면 힙에 push. dist와 대피소 갱신.

2. 새로운 경로가 기존 경로와 거리가 같고 대피소 번호가 더 작으면 힙에 push. dist와 대피소 번호 갱신.