백준_5719_거의 최단 경로
https://www.acmicpc.net/problem/5719
5719번: 거의 최단 경로
문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다. 거의 최단 경로란 최단 경로에 포함되지 않는 도로로만
www.acmicpc.net
해결 방법
> 한 마디로 2번째 최단 경로를 구하는 문제이다.
> 다익스트라를 돌리고 최단 경로를 저장(거리), 삭제(경로)
> 다시 한 번 다익스트라를 돌리고 최단 경로와 같다면 경로 삭제
> 다익스트라를 돌리고 다른 값이 나오면 이것이 2번째로 짧은 최단 경로!!!인 줄 알고 풀었으나 메모리 초과...
> 다익스트라를 돌리는 횟수가 많아서 그런 것 같다.
> 해결책 ----> 다익스트라(한 번) ----> dfs(같은 거리의 경로 모두 삭제) ----> 다익스트라 ----> 정답!!!
코드
import sys, heapq, copy
from collections import defaultdict
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
INF = float('inf')
def solve(adjacent, K):
prev = [-1] * (len(adjacent)) # predecessor
dist = [INF] * (len(adjacent)) # source로부터의 최소 거리 배열
dist[K] = 0
priority_queue = []
heapq.heappush(priority_queue, [0, K])
while priority_queue:
# 거리가 제일 작은 노드 선택
current_dist, here = heapq.heappop(priority_queue)
# 인접 노드 iteration
for there, length in adjacent[here].items():
next_dist = dist[here] + length
if next_dist < dist[there]:
dist[there] = next_dist
prev[there] = here
heapq.heappush(priority_queue, [next_dist, there])
return dist, prev
def dfs(here):
if here == end:
for i in route:
if i[1] in tmp[i[0]]:
tmp[i[0]].pop(i[1])
return
for i in range(num_place):
if adjacent[here][i] != float('inf') and dist[here] + adjacent[here][i] == dist[i]:
route.append((here, i))
dfs(i)
route.pop()
if __name__ == "__main__":
while True:
num_place, num_road = map(int, input().split())
if not num_road: #문제 조건 중 0 0이 들어오면 시스템 종료
break
start, end = map(int, input().split())
adjacent = [defaultdict(lambda : float('inf')) for _ in range(num_place)]
route = []
for _ in range(num_road):
a, b, p = map(int, input().split())
# 만약 동일한 경로의 간선이 주어질 경우 적은 비용의 간선 선택
if b in adjacent[a]:
adjacent[a][b] = min(adjacent[a][b], p)
else:
adjacent[a][b] = p
dist, prev = solve(adjacent, start)
tmp = copy.deepcopy(adjacent)
dfs(start)
dist, prev = solve(tmp, start) #경로 삭제 후 다익스트라
#탈출!!!
#거리가 inf이면 갈 수 없다는 뜻이므로 -1을 출력
if dist[end] == float('inf'):
print(-1)
else:
print(dist[end])