1916번 - 최소비용 구하기
낮은 priority queue를 이용한 정석적인 다익스트라 코드 (32ms)https://www.acmicpc.net/source...높은 priority queue를 사용했는데 통과 (40ms)https://www.acmicpc.net/source...그냥 stack, queue를 사용했는데 오히려 더 빨리 통과 (24ms) ..??https://www.acmicpc.net/source...https://www.acmicpc.net/source...다익스트라를 잘못 이해하고 있거나 실수해도 넘어갈수 있는 여지가 너무 많아서 테스트케이스를 더 추가해야할것 같습니다.
제가 고민을 좀 해봤는데 이런 케이스에 O(NMlogN)에 돌 것 같습니다. 또한, 위 그래프의 모든 간선이 0인 데이터도 해당 풀이를 막을 수 있을 것 같습니다.
그냥 문제 자체가 bfs로 풀어도 풀릴만큼의 시간이 널널한거같아요
시간제한이 0.5초라 O(NM)만 되어도 상수가 안작아서 터져야 해요
댓글을 작성하려면 로그인해야 합니다.
minbud 1년 전 4
낮은 priority queue를 이용한 정석적인 다익스트라 코드 (32ms)
https://www.acmicpc.net/source...
높은 priority queue를 사용했는데 통과 (40ms)
https://www.acmicpc.net/source...
그냥 stack, queue를 사용했는데 오히려 더 빨리 통과 (24ms) ..??
https://www.acmicpc.net/source...
https://www.acmicpc.net/source...
다익스트라를 잘못 이해하고 있거나 실수해도 넘어갈수 있는 여지가 너무 많아서 테스트케이스를 더 추가해야할것 같습니다.