[1504] 특정한 최단 경로

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

다익스트라 알고리즘 문제. 마찬가지로 Rhyno님이 작성한 힙을 사용했다.

 

풀이

1번에서 n번 정점까지의 최단경로, 하지만 반드시 두지점을 거쳐야 한다는 조건이 붙었다.

[1 -> v1 -> v2 -> n ] 또는 [1 -> v2 -> v1 -> n] 두 가지 최단 경로중 가중치가 더 적은 경로를 반환하면 된다. 1번 정점에서 각 정점으로 향하는 최단경로, v1 정점에서 각 정점으로 향하는 최단경로, v2 정점에서 각 정점으로 향하는 최단경로 총 다익스트라 3번을 돌린 뒤 각 가중치를 적절히 조합해서 반환하면 된다.

 

하지만 여기서 경로가 없는 조건에 대해 처리해주어야 하므로 이 부분만 신경 써준다면 정답을 받을 수 있다. 본인의 경우 최단경로를 담은 배열을 -1로 초기화한뒤 다익스트라를 통해 갱신하였는데, 아무리 조건을 신경 써서 제출해도 오답판정을 받아 결국 계산 가능한 가중치의 최댓값인 2억으로 초기화하며 예외처리하였다.

 

정답 코드