[백준 2307번] 도로검문 (Python3)

import sys
input = sys.stdin.readline
from heapq import heappush,heappop
INF = sys.maxsize

def Dijkstra():
  DP = [INF]*N
  hq = []
  heappush(hq,(0,0,0))

  while hq:
    w,now,last = heappop(hq)
    if DP[now] <= w:
      continue
    DP[now] = w
    path[now] = last
    for next,w1 in graph[now]:
      heappush(hq,(w+w1,next,now))
  return DP[-1]

def Dijkstra2(block):
  DP = [INF]*N
  hq = []
  heappush(hq,(0,0))

  while hq:
    w,now = heappop(hq)
    if DP[now] <= w:
      continue
    DP[now] = w
    for next,w1 in graph[now]:
      if (now,next)==block or (next,now)==block:
        continue      
      heappush(hq,(w+w1,next))
  return DP[-1]

N,M = map(int,input().split())

graph = [[] for i in range(N)]
for i in range(M):
  x,y,w = map(int,input().split())
  graph[x-1].append((y-1,w))
  graph[y-1].append((x-1,w))

path = {}
minimum = Dijkstra()
maximum = minimum
x = N-1
while path[x] != x:
  maximum = max(maximum,Dijkstra2((x,path[x])))
  x = path[x]

if maximum == INF:
  print(-1)
else:
  print(maximum-minimum)

간단한 다 익스트라 응용문제

 

다 익스트라를 한번 실행해서 최단거리와 경로를 구하고, 최단거리의 모든 경로를 한번씩 막아보면서 다 익스트라를 실행해서 최단거리의 최댓값을 구한 뒤 차이를 구하면 된다.

 

풀이를 떠올리는건 매우 쉬운데, 시간복잡도상 가능한 풀이인지를 생각하는게 헷갈렸다. 최악의 경우 다 익스트라를 1000번가량 실행해야 할 수도 있을 텐데, 가능할까 하는 의문. 결과적으로 맞는 풀이였다.

 

 

오늘의 교훈) 시간복잡도를 세심하게 계산하자