gallopsys   3달 전

우선 접근 방법은 최소 힙을 이용한 Dijkstra shortest-path 알고리즘을 채택하여 풀이를 시도하였습니다..

최소비용 구하기 문제에선 단순히 그 경로까지 갈 수 있는 최단거리를 출력하면 되는 문제였는데, 이번 문제는 경로되추적까지 포함되어 있어서 경로되추적 알고리즘을 Dijkstra 알고리즘 내에 추가하여 구현했는데요...

그런데 계속 WA를 받게 되어 질문을 드립니다.


경로되추적할 때, 가중치가 변경되는 경우 해당 노드의 부모 노드를 계속 갱신시켜주고, 최종 목표지점에 저장된 부모노드를 타고 내려가면 최종적으로 그 노드에 다다르지 않을까하고 경로되추적을 시도했는데 이렇게 시도하면 안 되나요..?


혹시 틀렸다면 어떤 테스트 케이스에서 걸리는지 궁금합니다...!

gallopsys   3달 전

INF 값이 0x700000(=‭7340032‬)로 최대 생각해볼 수 있는 케이스인 100000*1000 = 1억보다 작기 때문에 발생한 문제였습니다 ㅠㅜ

INF값을 0x7000000(=‭117440512‬)로 바꿔줬더니 AC 받았습니다...

댓글을 작성하려면 로그인해야 합니다.