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

문제

백준 1504번 - 특정한 최단 경로

해결 과정

• 조건

1. 무방향 그래프 -> 그래프 정의 다르게!
2. 반드시 거쳐가야하는 두 개의 정점: v1, v2를 합쳐서 경로 구하기
3. 1번부터 n번까지의 최단 경로

• 1번부터 v1,v2를 거쳐서 n번까지 가는 최단 경로

  • 시작점 -> v1 -> v2 -> n
  • 시작점 -> v2 -> v1 -> n

• 무방향 그래프 정의
  

• original_dist = dijkstra(1) : 1번부터 n까지 가는 최단 거리

• v1_dist = dijkstra(v1) : v1번부터 n까지 가는 최단 거리

• v2_dist = dijkstra(v2) : v2번부터 n까지 가는 최단 거리

• v1_v2 : 시작점 -> v1 -> v2 -> n

  • original_dist[v1] : 시작점 -> v1 거리
  • v1_dist[v2]: v1 -> v2 거리
  • v2_dist[n] : v2 -> n 거리

• v2_v1 : 시작점 -> v2 -> v1 -> n

  • original_dist[v2] : 시작점 -> v2 거리
  • v2_dist[v1] : v2 -> v1 거리
  • v1_dist[n] : v1 -> n 거리

풀이

import sys

# 정점 n ,간선 e
n,e = map(int,sys.stdin.readline().split())

graph = [[] for _ in range(n+1)]
# 무방향 그래프
# a정점에서 b정점까지 거리(가중치)는 c
for i in range(e):
  a,b,c = map(int,sys.stdin.readline().split())
  graph[a].append((b,c))
  graph[b].append((a,c))


# 반드시 거쳐야하는 서로 다른 두 개의 정점
v1,v2 = map(int,sys.stdin.readline().split())


INF = 1e9


import heapq
def dijkstra(start):
  distance = [INF] * (n+1)
  q = []
  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]))
  # start부터 n까지 가는 최단 거리
  return distance

# 출발점 1,v1,v2에서 n까지의 최단 거리
original_dist = dijkstra(1)
v1_dist = dijkstra(v1)
v2_dist = dijkstra(v2)


# 두가지 방법
# 시작점 -> v1-> v2 -> n
# 시작점 -> v2 -> v1 -> n
v1_v2 = original_dist[v1] + v1_dist[v2] + v2_dist[n]
v2_v1 = original_dist[v2] + v2_dist[v1] + v1_dist[n]

ans = min(v1_v2,v2_v1)

print(ans if ans < INF else -1)