BOJ 백준온라인져지 1504 특정한 최단 경로 풀이

1 -> N 의 최단거리를 구하면 된다.

조건 

1. v1 를 거쳐야 된다.

2. v2 를 거쳐야 된다.

3. 양방향 그래프다.

문제를 보니 민힙을 구현한 다익스트라를 사용해야 될 것 같았다.

풀이 방법

1 -> v1 -> v2 -> N
1 -> v2 -> v1 -> N

2 개중에 낮은 distance 를 출력하면 된다.

둘다 INF 면 -1 를 출력

다익스트라 알고리즘을 정리해보면

u -> v 의 minimum distance 를 구하는 알고리즘.

민힙을 사용해서 구현하면,

현재점을 startVertex, startVertex 에 연결된 점을 endVertex 라고 하자.

u -> startVertex -> endVertex 의 거리가

u -> 이미 간 점 -> endVertex 의 거리보다 작거나 처음 갱신한다면,

민힙에 push 해주고, 거리를 u -> startVertex -> endVertex 의 거리로 갱신해준다.

위의 3줄을 반복하면 정답이 나옴