[일반] pq + counting sort 기법 구현하는 법 아시는 분?

[익명(skuld88)]

아무리 봐도 다익스트라 쓰는 문제인데 다익스트라로 푸니 TLE남

간선 가중치가 1~100,000 이하 정수라는 조건이 있어서 (E = 100만)

다익스트라로 풀되, 간선 가중치 정렬할때 counting sort로 최적화 하라는게 정해같은데

이거 구현하시는 법 아시는분? 참고할만한 링크 주시면 감사하겠음

[익명(59.13)]

다익자체가 좀만 비효율적으로 구현해도 저격테케에 당하기 좋은데 그것도 체크해보셈

[익명(skuld88)]

그 큐에 넣을때 조건체크 빼먹어서 큐에 무한으로 계속넣는거 방지하는거 말하는건가요? 그 최적화는 되어있음

[익명(skuld88)]

https://pastebin.com/QvUaUb5U
다익스트라는 필요할때마다 이거 템플릿화해서 쓰고 있음 근데 counting sort로 하려니 어렵네요.

[익명(skuld88)]

혹시 이거 세그로 되나? 뇌정지 오네 시발

[익명(skuld88)]

아니 세그도 너무 어려운데... 간선 가중치만 10만 이하고 pq에서 비교하는건 vertex의 distance인데 이거는 10만 이하가 아님. 시발 어떻게 풀라는거지

[익명(121.130)]

문제 링크 있나여