[백준/Python] 1504번: 특정한 최단 경로
1504번: 특정한 최단 경로 (acmicpc.net)
1504번: 특정한 최단 경로
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존
www.acmicpc.net
문제 해석
방향성이 없는 그래프에서 주어진 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을 출력하도록 하였다.