글 읽기 - 14285번에 대해서 질문 있습니다.

(追記) (追記ここまで)

14285번 - 간선 끊어가기

안녕하세요.

14285번 문제에 대해서 생각한 제 로직이 맞다고 생각하는데 계속 틀리다고 나옵니다.

로직은 s에서 t로 가는 모든 path에 대해서 최단 경로만 빼고 다 제거 해줍니다.

그리고 나서 s에서 t로 가는 최단 경로 중에 최대 cost를 가지는 edge 하나만 제거하게 되면 s와 t는 비연결 상태가 되기 때문에 그 edge를 구했습니다.

이런 식으로 코딩을 했는데 제출을 하니 3%에서 계속 틀리다고 합니다. 제 틀린 논리에 대해서 짚어주시면 감사하겠습니다.

최단경로가 하나 이상일때도 처리가 잘 되나요?

조금 더 생각해보니까 굳이 최단경로만 남길 필요는 없을거 같습니다. ᅲᅲ

답변 감사합니다. 제가 짠 코드 결과에서는 7로 나오고 있습니다. pichulia님께서 말하신 최단 경로가 중복되는 경우에 대해서는 잘 처리하는 거 같습니다.

pichulia님께서 보여주신 반례를 보니 어떤 점이 잘못되었는지 알 수 있을 것 같습니다. 정말로 감사합니다.

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

(追記) (追記ここまで)

Baekjoon Online Judge