1948번 - 임계경로
문제에서 정점 수는 최대 10,000개, 간선 수는 최대 100,000개 입니다.
처음 다익스트라(최장으로 거리 갱신)를 사용하여 시작점에서 목표 점까지 도달하는 데에 O(E log E) = 약 1,700,000
이후 다시 시작점으로 역추적 탐색하는 시간 O(V + E) = 약 100,000
시간 초과는 나지 않을 것이라 생각하여 진행하였습니다.
제출한 결과, 약 3300ms로 문제에서 책정한 시간 제한 2초를 아득히 넘기는 수치이나 AC를 받았습니다.
혹시 왜 그런지 아시는 분 계신가요?
Java는 C++보다 느리기 때문에 시간 보너스가 주어집니다.
https://help.acmicpc.net/langu...
정확히는 시간 제한의 2배에 1초를 추가해준다고 합니다.
감사합니다!
댓글을 작성하려면 로그인해야 합니다.
yi9353 8달 전
문제에서 정점 수는 최대 10,000개, 간선 수는 최대 100,000개 입니다.
처음 다익스트라(최장으로 거리 갱신)를 사용하여 시작점에서 목표 점까지 도달하는 데에 O(E log E) = 약 1,700,000
이후 다시 시작점으로 역추적 탐색하는 시간 O(V + E) = 약 100,000
시간 초과는 나지 않을 것이라 생각하여 진행하였습니다.
제출한 결과, 약 3300ms로 문제에서 책정한 시간 제한 2초를 아득히 넘기는 수치이나 AC를 받았습니다.
혹시 왜 그런지 아시는 분 계신가요?