싸이클을 형성해서는 안된다는 조건을 추가해주세요.

해당 문제는 크루스칼 알고리즘 문제로 양의 가중치만이 존재할 경우에는 정점의갯수 -1개의 간선만 연결되는게 언제나 최적의 답이 됩니다. 즉 싸이클이 형성된다면 가중치의 총합이 상승하여 항상 오답이 됩니다.

하지만 문제에서는 음의 간선이 존재한다는 조건이 붙습니다. 음의간선이 존재하는 경우 전체 간선의 가중치의 총합이 최소가 되기위해서는 싸이클이 형성되더라도 모든 음의간선을 포함하는 스패닝트리가 그렇지 않은 스패닝트리보다 가중치를 낮출 수 있습니다.

이부분에서 모든 음의간선을 포함시켜서 계속 오답처리 되었습니다. 나중에 혹시나 싶어서 싸이클을 제거하니 정상 정답처리 됩니다. 문제에 해당 조건을 추가해주세요.