yi9353   8달 전

문제에서 정점 수는 최대 10,000개, 간선 수는 최대 100,000개 입니다.

처음 다익스트라(최장으로 거리 갱신)를 사용하여 시작점에서 목표 점까지 도달하는 데에 O(E log E) = 약 1,700,000

이후 다시 시작점으로 역추적 탐색하는 시간 O(V + E) = 약 100,000

시간 초과는 나지 않을 것이라 생각하여 진행하였습니다.

제출한 결과, 약 3300ms로 문제에서 책정한 시간 제한 2초를 아득히 넘기는 수치이나 AC를 받았습니다.

혹시 왜 그런지 아시는 분 계신가요?

luckyandykang   8달 전

Java는 C++보다 느리기 때문에 시간 보너스가 주어집니다.

luckyandykang   8달 전

https://help.acmicpc.net/langu...

정확히는 시간 제한의 2배에 1초를 추가해준다고 합니다.

yi9353   8달 전

감사합니다!

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