[백준] 1504번 특정한 최단 경로(python)

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

1. 난이도 골드4 (🥇)

 

2. 문제 해결 방법

다른 최단 경로 문제들과 다른 점은

 

1. 방향성이 없는 그래프이다(=양방향 모두 들릴 수 있다).

2. 두 정점을 반드시 거쳐야 한다.

 

1번은 graph에 append 할 때

 

for i in range(e):
  a,b,c = map(int, input().rstrip().split())
  graph[a].append((b,c))
  graph[b].append((a,c))

 

a,b 정점 모두에게 append 해주면 된다.

 

 

이제 2번을 해결해보자

 

우선 다익스트라의 정의는 한 지점에서 다른 지점까지의 최단거리를 나타내는 것이다. 

 

즉, 한 지점은 start일 필요가 없다.

 

예를 들어 반드시 거쳐야 하는 두개의 서로 다른 정점 번호가 v1, v2 라고 주어졌다고 했을때,

 

route1 = (start -> v1) + (v1 -> v2) + (v2 + end) 

route2 = (start -> v2) + (v2 -> v1) + (v1 + end)

 

이런 식으로 각각의 최단 거리를 모두 더하면 반드시 두 정점을 거치는 최단거리가 도출된다.

 

또한 양방향 그래프이기 때문에 v1을 먼저 들릴 때(route1), v2를 먼저 들릴 때(route2)를 모두 구해서 최솟값을 출력하면 된다.

 

 

3. 내가 작성한 코드

import heapq
import sys

n,e = map(int,input().rstrip().split()) #n정점 e간선

INF = int(1e9)
graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)

for i in range(e):
  a,b,c = map(int, input().rstrip().split())
  graph[a].append((b,c))
  graph[b].append((a,c))

def dij(start, end):
  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]))
  
  return distance[end]

v1, v2 = map(int,input().rstrip().split())

route1 = dij(1,v1) + dij(v1,v2) + dij(v2,n)
route2 = dij(1,v2) + dij(v2,v1) + dij(v1,n)

x = min(route1, route2)

if x >= INF:
  print(-1)
else:
  print(x)

 

 

다익스트라를 실행시킬 때마다 distance list를 초기화 시켜줘야 하는데 그걸 안 해서 계속 틀렸었다.