2645번 - 회로배치
회로가 여러개가 겹쳐있고, 겹쳐있는 부분이 최단경로의 일부일때 그 지점의 cost를 단순 K가 아닌 n*K (n=회로가 겹친 횟수)로 해도 통과가 됩니다.
이를 걸러낼 데이터를 추가했으면 좋겠습니다.
오답 출력하는 코드: https://www.acmicpc.net/source...
예시:
5x5 지도에서 만약 두 회로가 2번 열을 완벽히 가로지를때
0 1 0 0 0
지도를 이렇게 회로 지나가는 지점들의 cost를 K로 저장하는 것이 맞는데
0 2 0 0 0
이렇게 n*K로 처리해도 정답으로 뜹니다.
회로 여러개 지나가는 지점이 필연적으로 최적경로에 해당하는 경우에 이런 일이 생깁니다.
https://www.acmicpc.net/board/...
해당 데이터에서 오답을 출력하는 코드의 제출 번호를 기입해 주세요.
위 댓글 수정했습니다.
감사합니다
댓글을 작성하려면 로그인해야 합니다.
joykim26 11달 전
회로가 여러개가 겹쳐있고, 겹쳐있는 부분이 최단경로의 일부일때 그 지점의 cost를 단순 K가 아닌 n*K (n=회로가 겹친 횟수)로 해도 통과가 됩니다.
이를 걸러낼 데이터를 추가했으면 좋겠습니다.
오답 출력하는 코드: https://www.acmicpc.net/source...
예시:
5x5 지도에서 만약 두 회로가 2번 열을 완벽히 가로지를때
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0
0 1 0 0 0
지도를 이렇게 회로 지나가는 지점들의 cost를 K로 저장하는 것이 맞는데
0 2 0 0 0
0 2 0 0 0
0 2 0 0 0
0 2 0 0 0
0 2 0 0 0
이렇게 n*K로 처리해도 정답으로 뜹니다.
회로 여러개 지나가는 지점이 필연적으로 최적경로에 해당하는 경우에 이런 일이 생깁니다.