[BOJ][Python] 백준 9370번 - 미확인 도착지

문제 링크: https://www.acmicpc.net/problem/9370

9370번: 미확인 도착지

---

문제 풀이

데이크스트라

 

처음에는 g와 h를 방문 했는지에 따라 처리를 했었다. g-h혹은 h-g를 방문했다고 체크를 하면서 해당 번호에 저장을 했었다. 문제는 가중치가 같은데 하나는 g-h 간선을 방문했고 하나는 방문을 안했다면 덮어질 수도 있다. 이 점까지 체크했고 정답을 확신 했었다. 하지만 이제는 시간 초과가 나기 시작했다. 아무래도 가중치가 같은 값이 수없이 많으면 또 그만큼 돌려야하니깐 시간초과가 일어날 수 밖에 없다. 따라서 가중치도 같으면서 방문했는지에 대한 여부를 동시에 할 순 없을까?

 

바로 g-h 간선의 가중치를 손봐주면 된다. 단 티가 안날 정도로 해줘야한다.

데이크스트라는 시간복잡도를 줄이기 위해서 우선순위 큐를 사용하는데 가중치가 같다면 g-h 간선으로 간 것을 우선순위를 높혀야 한다. g-h 간선을 0.01정도 줄이면 가지 않은 것보다 0.01만큼 차이나기 때문에 g-h 간선을 간 것을 우선처리 하게 된다. 그러면 자연스럽게 중복된 것들을 처리도 할 수 있다. 또한 간선을 지나갔으면 (파이썬 기준으로) 정수 값에서 실수값이 되었으므로 INF가 아니고 타입이 float라면 g-h 간선으로 이동했고 최단거리로 이동했다는 뜻이므로 이 부분만 잘 처리하면 된다.

 

코드

	from heapq import *
	import sys
	input = sys.stdin.readline
	INF = int(1e9)
	for _ in range(int(input())):
	n, m, t = map(int, input().split())
	s, g, h = map(int, input().split())
	graph = [[] for _ in range(n+1)]
	dist = [INF for _ in range(n+1)]
	for _ in range(m):
	a, b, c = map(int, input().split())
	if (a == g and b == h) or (a == h and b == g):
	graph[a].append((b, c-0.01))
	graph[b].append((a, c-0.01))
	else:
	graph[a].append((b, c))
	graph[b].append((a, c))
	f = []
	for _ in range(t): f.append(int(input()))
	f = sorted(f)
	heap = []
	heappush(heap, (0, s))
	while heap:
	d, now = heappop(heap)
	if d > dist[now]: continue
	for i in graph[now]:
	cost = d+i[1]
	if cost < dist[i[0]]:
	dist[i[0]] = cost
	heappush(heap, (cost, i[0]))
	ans = []
	for i in f:
	if dist[i] != INF and type(dist[i]) == float: ans.append(i)
	print(*ans)

view raw 9370.py hosted with ❤ by GitHub