redcube231   1년 전

1000개의 선분에 대해 발생 가능한 교점의 수 = 정점의 수 V = 500'000개, 간선의 수 E = V * 2인 그래프에 대해 데이크스트라를 테스트케이스 100개만큼 실행할 경우 시간복잡도는 O(TElogV) = O(100 * 1'000'000 * 18) 이며 이는 대략 18억회 연산입니다(실제로는 T가 125까지 커질 수 있다고 하니 더 큽니다).

이전 글들에서 이론상 최대 교점의 절반 정도가 최대로 발생한다는 점이 발견된 것도 그렇고, 계산 가능한 최악의 시간에 비해 제가 단축한 시간이 극도로 짧습니다.

그리고 sum(M_i) 도 1540 인 점 등 문제에 문제가 많습니다.

문제에 이를 설명하는 추가 조건을 명시하거나 제한 시간을 늘려야할 거 같은데 어떻게 생각하시나요?

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