시간 초과가 나는 것은 13번 루프가 말해주듯 우선순위를 모든 점을 보면서 구하고 있기 때문입니다. 힙 자료구조를 사용해 보세요.
덤으로, dict에 원소가 들어있는지 없는지에 따라 생기는 귀찮은 분기를 줄이기 위해 collections 모듈의 defaultdict를 이용하면 편합니다.
1939번 - 중량제한
힙 자료구조를 이용했는데도 시간 초과가 뜨네요 어디서 줄일 수가 있을까요?
import heapq N, M = map(int, input().split()) def dijkstra(l, s, e, N): heap = [] check = dict() distances = {_: float("inf") for _ in range(N + 1)} for i in range(1, N+1): if i in l[s]: if l[s][i] != 0: distances[i] = l[s][i] heapq.heappush(heap, (-distances[s], s)) while heap: if check.get(e) is not None: break maxVal, maxIdx = heapq.heappop(heap) if maxIdx in check: if check[maxIdx]: continue else: check[maxIdx] = True for c, c2 in l[maxIdx].items(): if check.get(c): continue if distances[maxIdx] < distances[c] != float("inf") and distances[maxIdx] != float("inf"): continue else: t = distances[maxIdx] if t > c2: t = c2 if distances[c] == float("inf"): distances[c] = t elif distances[c] < t: distances[c] = t heapq.heappush(heap, (-distances[c], c)) return distances l = {} for i in range(N + 1): l.update({i: {}}) for i in range(M): A, B, C = map(int, input().split()) if l[A].get(B) is not None and l[A].get(B) < C: l[A] = {B: C} l[B] = {A: C} else: l[A].update({B: C}) l[B].update({A: C}) s, e = map(int, input().split()) check = [False for i in range(N + 1)] check[s] = True dist = dict() dist = dijkstra(l, s, e, N) if dist.get(e) is None: print(0) else: print(dist[e])
댓글을 작성하려면 로그인해야 합니다.
doubleyyh 2년 전
안녕하세요. 파이썬 어린이입니다. 시간 초과가 뜹니다. 어디에서 줄일 수 있을까요? 더해서 제가 파이썬 초보라서 코드 피드백도 해주시면 감사하겠습니다.