plzrun   10달 전

아래와 같이 코드를 짰는데,

어느부분에서 에러인지 잘 모르겠습니다.


에러 케이스 하나만 짚어주실 수 없나요?

채점중 4%에서 '틀렸습니다' 뜨는데요,

밑에 just for the test 부분으로 주석처리되어있는거 해제하면

어떤 경로로 진행해서 답이나오는지 보여줍니다.



-------------------------------------------------------------------------------------------------------------------

코드에 대한 지적도 해주시면 감사해요. (바쁘시면 틀린 입력케이스만이라도 부탁드릴게요.)

해당 코드는 프림 알고리즘을 기반으로 작성했는데요,

s----->t (가중치 c)로 표현하였고, 이것을 inputE.target = t, inputE.cost = c를 한 다음

vector변수인 v에다가 v[s].push_back(inputE)를 하여 그래프를 구성하였습니다.


그래서 그래프 v[s][ i ]에서 i를 1씩 증가시키면서 s노드에 인접한 노드들의 번호와 가중치를 접근하고 그 가중치들로 minHeap을 구성하여 항상 최소가 되는 가중치를 뽑도록 했어요.


기타 자질구레한 예외사항들 처리한 부분은 continue 써져있는 부분입니다.

cubelover   10달 전

5 7
1 2 1
1 3 1
1 4 1
2 3 1
2 4 1
3 4 1
4 5 2

이런 데이터에서 답이 5인데 3을 출력하네요

plzrun   10달 전

답변 감사합니다~!

plzrun   10달 전

cubelover

덕분에 맞았습니다. ㅎ

혹시라도 질문 검색하실 분들을 위해 몇마디 적어보자면,

보니까 1--->2 (가중치1), 4--->2 (가중치1)인 경우

target(노드 번호를 의미):2, cost(가중치):1로 같은데도 불구하고 heap에 중복되게 삽입되는게 문제였어요.

일단은 heap이 비어있지 않으면 반복문을 계속 돌도록 해서 해결했는데,

중복 추가 자체를 안하게 한번 바꿔봐야겠습니다.

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