u와 v사이의 경로가 있으면 이 그래프의 최소 가중치 간선을 그래프에서 제거한다. 이 과정을 u와 v사이의 경로가 없을 때까지 반복한다.
그러므로 저 예시에서는 Cost값은 무조건 0, 2, 2 + 3, 2 + 3 + 4, 2 + 3 + 4 + 5 중 하나가 돼야 합니다. Cost = 7은 불가능한 경우에요 아마 경로상의 최소 가중치 간선으로 착각하신 것 같네요
실제로 계산해보면
Cost(1, 2) = 2 + 3 + 4 = 9
Cost(1, 3) = 2 + 3 + 4 + 5 = 14
Cost(2, 3) = 2 + 3 + 4 = 9
Cost(4, 5) = 2
라서 답은 34가 맞습니다.
hongjg3229 2년 전
많은 코드들에서 해당 컴포넌트가 가중치 0인 존재하지 않는 간선으로 연결되어있다고 취급하고 34를 출력합니다. 하지만 올바르게 계산하면 cost(1,2)=7, cost(1,3)=12, cost(2,3)=7, cost(4,5)=2, 그외 cost는 0이므로 28이 답이 됩니다.
오답을 출력하는 코드 : https://www.acmicpc.net/source...