Search

[백준 1504] 특정한 최단 경로

[백준 1504] 특정한 최단 경로

Tip

플로이드 워셜로도 풀 순 있지만, N이 최대 800이므로 O(N³)이므로 시간 초과
→ 다익스트라 알고리즘 사용
기본적인 다익스트라 알고리즘 함수에서 다른 점
중간점(v1, v2)를 거쳐 지나가야하기 때문에 출발 지점에서 종착 지점까지의 다익스트라 연산 외 여러번의 연산이 필요
dijkstra(start, v1), dijkstra(v1, v2), dijkstra(v2, fin)...
v1 → v2보다 v2 → v1의 경우가 더 빠를 수 있으므로, 두 경우 중 최솟값을 출력
min()함수 사용

풀이 소스 코드

import heapq import sys si = sys.stdin.readline INF = int(1e9) # 정점 개수 및 간선 개수 입력 n, e = map(int, si().split()) start = 1 # 2차원 리스트 생성 graph = [[] for _ in range(n + 1)] # 정점과 간선 간의 정보 입력 for _ in range(e): a, b, c = map(int, si().split()) graph[a].append((b, c)) graph[b].append((a, c)) # 중간점 정보 입력 v1, v2 = map(int, si().split()) # 다익스트라 알고리즘 def dijkstra(start, fin): q = [] distance = [INF] * (n + 1) heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if distance[now] < dist: continue for i in graph[now]: cost = dist + i[1] if cost < distance[i[0]]: distance[i[0]] = cost heapq.heappush(q, (cost, i[0])) return distance[fin] result = min(dijkstra(start, v1) + dijkstra(v1, v2) + dijkstra(v2, n), dijkstra(start, v2) + dijkstra(v2, v1) + dijkstra(v1, n)) if result >= INF: print(-1) else: print(result)
Python