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번가량 실행해야 할 수도 있을 텐데, 가능할까 하는 의문. 결과적으로 맞는 풀이였다.
오늘의 교훈) 시간복잡도를 세심하게 계산하자