13907번 - 세금
고수 선생님들께 여쭤봅니다.
이런 2차원 dp 최단거리 문제에서
왜 heapq 를 사용하는 djikstra 보다 deque를 사용하는 BFS + 가지치기가 더 빠른건가요?
heapq TLE : 100846469
deque pass : 100847464
몇몇 문제들에서 비슷한 상황을 겪었는데 이해가 잘 안되어서요.ㅜㅜ
시간복잡도 자체가 다르게 계산되니까요
댓글을 작성하려면 로그인해야 합니다.
cj98123 11달 전
고수 선생님들께 여쭤봅니다.
이런 2차원 dp 최단거리 문제에서
왜 heapq 를 사용하는 djikstra 보다 deque를 사용하는 BFS + 가지치기가 더 빠른건가요?
heapq TLE : 100846469
deque pass : 100847464
몇몇 문제들에서 비슷한 상황을 겪었는데 이해가 잘 안되어서요.ㅜㅜ