문제 자체는 다익스트라를 이용해도 맞는 문제이긴 합니다만, 틀리셨다고 하면 작성하신 코드가 잘못되지 않았나 싶습니다.
다익스트라에서 dist에 넣으신 초기값이 너무 작습니다.
간선이 최대 100000개에 가중치가 최대 100000이면 이론상 10^10까지 가능하지않을까요?
아래에 벨만-포드에는 초기값이 충분히 크게 작성되어있는 것으로 보아 그 문제일수도 있다는 생각이 듭니다!
1916번 - 최소비용 구하기
아 저거 혹시나 너무크게줘서 그런가 싶어서 바꾼 상태였습니다!
1억 10억 100억했어도 안됐었습니다..
그리고 추가로
큐에다 넣을때 그리고 뺄때 거리에 곱하기 -1을 하는건 내림차순으로 정렬해주기 위해서 배운 방식을 쓴겁니다
근데 지금 친구코드와 비교해보고 혹시나 싶어 greater을 이용해 넣어줬더니 맞았습니다...
이유를 잘 모르겠습니다;; 간선이 0이 들어올수 있는것과 관계가있을거같은데...
"간선이 0이 들어올수 있는것과 관계가있을거같은데..."
그렇습니다. 문제가 되는 곳은 q.pop()의 위치입니다. 간선의 가중치가 0일 수 있기 때문에 cur_node로부터 next_node를 거리가 같은 것으로 갱신할 수 있고, 그렇게 되면 q에 cur_dist와 같은 거리를 가진 다른 원소가 또 삽입됩니다. 만일 next_node (정점 번호)가 cur_node보다 크다면 pair의 비교 연산법에 의해 q의 top에는 next_node가 들어가 있을 것이고, 그래서 엉뚱한 원소를 pop하게 됩니다. q.pop()은 42번째 줄 직후에 있어야 합니다.
물론 거리의 초기값도 고치셔야 합니다.
그리고 그것만 바꾸면 시간 초과를 받게 되는데, 그 이유는 https://infossm.github.io/blog... 에서 찾으실 수 있습니다.
정말 너무감사합니다 선생님 블로그 글 한참들여다보고 이제서야 이해했습니다ㅠㅠㅠㅠ
다익스트라는 돌아가는걸 완전히 이해하는게 조큼 힘든거같네요... 플로이드나 벨만은 그래도 이해는됐는데...
너무 대단하십니다 커피한잔 사드리고싶습니다 여기 왜 쪽지기능이 없죠??
벨만은 이제보니 그렇네요... 출발하는 정점이 방문한 것만 돌리는거니까...
너무너무 감사합니다!!!
추가로 greater로 바꾸신 코드 역시 로직에 문제가 있지만 데이터가 약해서 통과된 것이기 때문에 모두 데이터 추가 요청을 올렸습니다.
그럼 혹시 선생님 글 보고 수정한 이 코드도 틀린부분이 있을까요??
댓글을 작성하려면 로그인해야 합니다.
dudcks0994 3년 전
처음에 다익스트라로 푸는문제인거같아서 풀었는데 2퍼에서 무조건 틀리더라구요
그래서 해보다 계속 똑같길래 벨만포드로 풀었는데, n-1번 돌렸는데 92퍼에서 틀리는겁니다
그래서 뭐지??해서 n번 돌리니까 맞았습니다;;
왜 다익스트라로 안풀리는건지, 왜 벨만포드로 n-1번이 아닌 n번을 돌려야 하는건지 잘 모르겠습니다