hayman42   4년 전

일단 최악의 경우 관계가 1000만번 들어올 수 있는데 100ms 만 걸리는 것으로 보아 입력이 매우 많은 경우가 없는 것으로 보입니다.

그리고 https://www.acmicpc.net/source/13336453 와 같이 간선이 불필요하게 여러번 탐색되는 경우에 대해서도 시간이 거의 똑같이 걸리는 것으로 보아 이에 대한 케이스가 없는 것으로 보입니다.

따라서 아래 코드로 생성 되는 데이터를 추가해주세요.

나름 문제의 조건에 맞게 데이터를 생성한다고 검수했는데 혹시 잘못 된 부분 있으면 부탁드리겠습니다.

djm03178   4년 전

테스트 케이스의 수의 최댓값이 명시가 되어있다고 하더라도, 출제자의 의도는 모든 케이스에서 최대 입력을 넣는 것이 아닌 경우가 많습니다. 개별 케이스에서 오래 걸리는 입력을 넣는 것은 괜찮겠지만, 빡센 케이스를 최대 개수만큼 채워넣는 것은 문제의 의도와는 다를 수 있다고 우려됩니다.

hayman42   4년 전

@djm03178 테케 수가 명시되어 있고 빡센 케이스로 다 채우지 않는 경우 빡세지 않은 케이스에 의해 희석 되서 사실상 빡세지 않은 케이스만 있게 되는거나 마찬가지라서 저렇게 다 넣어본건데 말씀도 일리가 있습니다. 사실 제가 혼자 테스트 해 본 결과 일반적인 다익스트라 풀이도 1.5 초 넘게 걸려서 이렇게 해야하나 싶긴 했습니다. 그런데 중복 처리 안한 다익스트라 풀이는 거의 3배가 넘는 시간이 걸렸기도 했고, 사실 제가 올린 케이스보다도 더 심각한 케이스도 분명히 존재 할 것이기 때문에 이런 케이스를 올린 것 입니다. 제 생각에도 사실 1000만개의 입력은 다익스트라 돌리는 것에 비해 너무 시간을 많이 먹어서 좀 조정할 필요는 있어 보이지만, 적어도 저런 케이스의 비율이 높은 테스트케이스는 있어야 한다고 생각합니다. 그리고 정 입력이 너무 많은 경우가 좀 아니다 싶으면 총 간선 수의 상한을 명시해도 될 것 같습니다.

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