[백준1504&파이썬] 다익스트라에서 특정정점을 무조건 방문해야할때, 다익스트라는 시작정점으로부터 최단경로를 보장한다.

# 문제

백준 1504 파이썬 특정한 최단 경로 풀이

1504번: 특정한 최단 경로

# 코드

'''
  - 임의로 주어진 두 정점을 반드시 통과해야 한다.
  - 한번 이동했던 정점과 간선도 다시 이용할 수 있다.
  - 1번 정점부터 N번 정점으로 이동한다.
'''
import sys
from heapq import *
from collections import defaultdict

N, E = map(int, sys.stdin.readline().split())  # N : 정점의 개수 , E : 간선의 개수
graph = defaultdict(list)
for _ 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())


# 두개의 정점을 무조건 지나면서 최단 경로의 길이를 구해야 한다.
# 1 -> v1 -> v2 -> N
# 1 -> v2 -> v1 -> N
def dijkstra(start, end):
  heap = list()
  distance = [float('inf')] * (N + 1)
  distance[start] = 0
  heappush(heap, (0, start))

  while len(heap) != 0:
    cur = heappop(heap)  # (sum_weight, vertex )

    if distance[cur[1]] < cur[0]:
      continue

    for next in graph[cur[1]]:  # ( vertex, weight )
      cost = distance[cur[1]] + next[1]
      if cost < distance[next[0]]:
        distance[next[0]] = cost
        heappush(heap, (cost, next[0]))

  return distance[end]


# print(f"(v1, v2) : ({v1},{v2})")
result = min(dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N), dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N))
if result == float('inf'):
  print(-1)
else:
  print(result)

 

# 풀이

result = min(dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N), dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N))
if result == float('inf'):
  print(-1)
else:
  print(result)

• 결론적으로, 1 -> v1 -> v2 -> N 또는 1 -> v2 -> v1 -> N 두개의 경로중 가장 작은걸 반환 시키면 된다.
• 내가 고민했던건 [ 1 -> v1 ->v2 -> N ]의 경로에서 1->v1 의 경로가 v2를 거치는걸 어떻게 확인하는지 였다. 그러나 만약 v2를 거쳤다면, 해당 경로가 선택 되는 것이 아닌 [1 -> v2 -> v1 -> N ]가 최종 선택 되기 때문에 고민하지 않아도 된다.
• https://www.acmicpc.net/board/view/99286 해당 질문과 같은 비슷한 고민을 했는데 이 고민 역시 바로 위 해결책과 동일하다. 결국 다익스트라는 시작경로에서부터 모든 정점까지의 최단거리가 구해진다.
• float('inf') + 1 도 INF 이다. 그렇기 때문에 조건문에서 검사할때 result == float('inf')로 하면 된다. float('inf') -1도 마찬가지다.