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

문제 링크

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

1504번: 특정한 최단 경로

풀이 

- 모든 지점에서 다른 모든 지점까지의 최단 거리를 구하는 알고리즘인 플로이드 워셜 알고리즘을 사용했는데 시간초과가 발생하였다.

- 플로이드 워셜의 시간 복잡도 : O(N^3)

# 플로이드 워셜 풀이 : 시간 초과 
n, e = map(int,input().split())

INF = int(1e9)

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

# 자기 자신까지의 거리 0 으로 초기화 
for i in range(1,n+1):
  for j in range(1,n+1):
    if i == j : 
      graph[i][j] = 0 
    
for _ in range(e):
  a, b, c = map(int,input().split())
  graph[a][b] = c
  graph[b][a] = c 

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

# 모든 지점에서 다른 모든 지점까지의 최단 거리 구하기 
for k in range(1,n+1):
  for a in range(1,n+1):
    for b in range(1,n+1):
      graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# a -> v1 -> v2 -> b 경로로 가는 것과 a -> v2 -> v1 - > b 경로 최솟값 구하기 
answer = min(graph[1][v1]+graph[v1][v2] + graph[v2][n], graph[1][v2]+graph[v2][v1] + graph[v1][n])

# 그러한 경로가 없다면 -1 출력 
if answer >= INF :
  print(-1)
else:
  print(answer)

- 다익스트라로 변경하여 풀었더니 통과 

- 다익스트라의 시간 복잡도 : O(Elog(V))

import heapq 

def dijkstra(start,end):
  distance = [INF] * (n+1)
  distance[start] = 0
  q = []
  heapq.heappush(q,(0,start))

  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]
  
n, e = map(int,input().split())

INF = int(1e9)

graph = [ [] for _ in range(n+1) ]
    
for _ in range(e):
  a, b, c = map(int,input().split())
  graph[a].append((b,c))
  graph[b].append((a,c))

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

answer = min(dijkstra(1,v1) + dijkstra(v1,v2) + dijkstra(v2,n), dijkstra(1,v2) + dijkstra(v2,v1) + dijkstra(v1,n)) 

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