BOJ
[Python 3] BOJ - 1504 "특정한 최단 거리"
PeiSea
2020. 3. 19. 20:31
# 문제 링크 : https://www.acmicpc.net/problem/1504
1504번: 특정한 최단 경로
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호가 주어진다.
www.acmicpc.net
# 풀이 :
개인적으로 문제의 핵심은 출발점이 정해져 있다는 것이다. 따라서 반드시 거쳐야 하는 두 점을 x, y라고 한다면 경우를 나눠 볼 수 있다.
1. 정점 1 → 정점 x → 정점 y → 정점 N
2. 정점 1 → 정점 y → 정점 x → 정점 N
가능한 두 가지 경로 중 더 짧은 거리가 문제에서 요구하는 답이므로 경로 1과 경로 2의 리턴값을 비교해주면 된다. 만일 정점 1과 2 모두 INF값을 가진다면 어떠한 경우에도 1번 정점에서 출발하여 x, y를 거쳐 N번 정점으로 갈 수 없다는 뜻이므로 -1을 출력한다. 또한 다익스트라 알고리즘에서 시간을 줄이기 위해 리스트보다는 힙을 자료구조로 이용하였다. 따라서 모든 정점에서 다익스트라를 실행하지 않고 1번 부터 N번 정점 까지의 다익스트라를 총 두번 실행하면 된다.
# 코드
import sys,heapq
# 초기 무한대값
INF = 100000000000000000000
n, m = map(int, sys.stdin.readline().split())
# 인접 리스트 생성
adj = [[] for _ in range(n)]
for _ in range(m):
a, b, c = map(int, input().split())
adj[a-1].append([b-1, c])
adj[b-1].append([a-1, c])
# 반드시 지나야 하는 두 정점 입력
x, y = map(int, sys.stdin.readline().split())
# dijkstra : depart 에서 시작하여 arrive 까지 가는데 드는 최소비용을 리턴하는 함수
def dijkstra(depart, arrive):
dist = [INF]*n
pq = []
heapq.heappush(pq, (0, depart))
dist[depart] = 0
while pq:
cost, now = heapq.heappop(pq)
if dist[now] < cost:
continue
for nxt, ncost in v[now]:
ncost += cost
if dist[nxt] > ncost:
dist[nxt] = ncost
heapq.heappush(pq, (ncost, nxt))
return dist[arrive]
# path1 : 1, x, y, n 순서일 때 최소 비용
# path2 : 1, y, x, n 순서일 때 최소비용
path1 = dijkstra(0, x-1) + dijkstra(x-1, y-1) + dijkstra(y-1, n-1)
path2 = dijkstra(0, y-1) + dijkstra(y-1, x-1) + dijkstra(x-1, n-1)
ans = min(path1, path2)
print(ans if ans < INF else "-1")