import sys
input = sys.stdin.readline
from heapq import heappush, heappop
from collections import deque
INF = 10**9
def Djikstra():
DP = [INF]*N
hq = []
hq.append((0,start,start))
while hq:
w,now,last = heappop(hq)
if DP[now] < w:
continue
if DP[now] == w:
path[now].append(last)
continue
DP[now] = w
path[now] = [last]
for next in range(N):
w1 = graph[now][next]
if w1 != INF:
hq.append((w+w1,next,now))
return DP[end]
def delete():
dq = deque([(end,end)])
while dq:
now,next = dq.popleft()
if graph[now][next] == INF:
continue
graph[now][next] = INF
for last in path[now]:
dq.append((last,now))
while True:
N,M = map(int,input().split())
if (N,M) == (0,0):
break
start,end = map(int,input().split())
graph = [[INF]*N for i in range(N)]
graph[end][end] = 0
for i in range(M):
x1,x2,w = map(int,input().split())
graph[x1][x2] = w
path = {}
shortest = Djikstra()
if shortest == INF:
print(-1)
continue
delete()
short = Djikstra()
if short == INF:
print(-1)
else:
print(short)
기본적인 알고리즘은 떠올리기 매우 쉽다.
간단하게 요약하면
1. 다 익스트라로 최단거리 탐색, 이때 최단거리의 경로까지 저장해주어야 한다.
2. 저장된 최단거리 경로의 간선 삭제
3. 다 익스트라로 최단거리 탐색 (거의 최단경로)
여기까지는 누구나 떠올릴 수 있지만, 실수할 수 있는 포인트가 매우 많았다. 내가 한 실수들을 정리하면
1. 다 익스트라를 한번써서 경로를 한개 지우고, 다익스트라 한번 더 써서 이전의 거리와 같으면 경로 한개 더 지우고 하는 식으로는 풀 수 없다. 모든 최단 경로를 한번에 다 찾아야한다.
(이유: 시간초과도 문제이지만 최단경로들이 노선을 공유하는 경우 모든 최단경로를 지울 수 없다.)
2. BFS 하는 과정에서 지나간 곳인지 check하지 않으면 메모리초과 or 시간초과가 발생한다.
(이유 : 같은 노선을 공유하는 경우 중복해서 실행됨)
3. check하기 위해서 visited 리스트를 사용한다면 1차원 리스트로 만들어선 안된다. 그러면 해당 노드를 지나는 서로 다른 간선을 모두 지울 수 없다.
4. BFS 도중 시작지점이 나왔다고 해서 함수를 끝내선 안된다. 모든 노선을 지울 수 없다.
대략 이 정도가 될 것이다.
계속해서 틀렸습니다 가 나와서 짜증나는 문제였지만 BFS와 다 익스트라에 대해서 좀 더 깊은 이해를 할 수 있게된 문제였던 것 같다.
오늘의 교훈) BFS에서 지나온 곳을 항상 체크하자