아직 완전히 감이 잡히지는 않았지만 슬랙에서 많은 분들이 도움을 주셔서 다른 분들도 보실 수 있게 댓글로 남깁니다 :)
1. 음수 간선이 존재하거나
2. 최장거리를 구하는 문제에선
다익스트라 알고리즘이 제대로 돌아가지 않을 수 있으며, 실제로 최장거리를 구하는 문제는 NP-Hard라고 합니다.
lky님께서 남겨주신 링크: https://en.wikipedia.org/wiki/Longest_path_problem
이 문제에서 K가 10 이하이고, 리프트를 제외하곤 DAG라서 가능하지 않을까 했는데.. 아직 완전히 감이 잡히진 않지만 좀 더 공부해봐야겠습니다 :)
슬랙에 도움주신 분들 모두 감사드립니다.
kth990303 2년 전 1
KCM Travel 문제처럼 dijkstra로 접근하되,
최단경로 문제가 아니기 때문에 우선순위 큐 operator() 를 아래와 같이
리프트횟수를 최소인 우선순위로, 거리를 최대인 우선순위로 우선순위큐 cmp를 설정하여 접근해보았습니다.
O(10*2*MlgN)일 줄 알았는데 시간초과가 나더라구요.
우선순위 큐 cmp를 다르게 설정하여 다익스트라로 풀리지 않는 이유(시간초과가 나는 이유)가 궁금합니다.