[백준/Python] 1504번: 특정한 최단 경로

1504번: 특정한 최단 경로 (acmicpc.net)

1504번: 특정한 최단 경로

---

문제 해석

방향성이 없는 그래프에서 주어진 2가지의 노드를 거친 1번 노드에서 N번 노드까지의 최단거리를 구하는 문제이다.

만약 경로가 없을 경우, -1를 출력한다.

---

코드

---

문제 풀이

3번의 다익스트라를 사용하여 문제를 풀었다.
1번 노드에서 출발하는 다익스트라를 통해 1번 노드 -> 중간노드1, 1번노드 -> 중간노드2의 거리를 구하고
중간노드1에서 출발하는 다익스트라를 통해 중간노드1 -> 중간노드2, 중간노드1 -> N번노드의 거리를,
중간노드2에서 출발하는 다익스트라를 통해 중간노드2 -> N번노드의 거리를 구했다.

코드를 살펴보면
각 값을 입력받고 arr에 인접리스트를 저장해주었다. 경로상 거칠 두 노드는 v1, v2로 선언해주었다.

그 후, heapq에 [0, 1]을 넣어 첫번째 다익스트라를 실행해주고 stov1에 1번 -> v1의 거리를, stov2에 1번 -> v2의 거리를 저장했다.

두번째 다익스트라에선 v1tov2에 v1 -> v2 혹은 v2 -> v1의 거리를 저장하였고 v1toN에 v1 -> N번의 거리를 저장해주었다.

세번째 다익스트라를 통해 마지막 인자를 구해주고 각 값들을 더해 최소값을 출력해주었는데
만약 경로가 없을 경우 -1를 출력해야하므로 두 경로 모두 float('inf')를 넘어갈 경우, -1을 출력하도록 하였다.