yechance   4년 전

다익스트라 알고리즘을 써서 올바른 답은 출력하는데,, 시간초과가 됩니다 ㅠㅠ
코드에서 뺄것도 없어보이고,, 어떻게 수정해야 빨라지는지 모르겠습니다ㅠㅠ 도와주세요 ㅠㅠ

portableangel   4년 전

이 문제의 제목이 플로이드인 이유는 플로이드-워셜 알고리즘을 사용하여 푸는 문제이기 때문입니다.

다익스트라를 쿼리마다 돌리는 경우엔 시간복잡도가 너무 커 통과하기가 어렵습니다.

portableangel   4년 전

그런데 지금 다시 보니 제한이 좀 작아서 O(MlogN) 다익스트라로도 풀 수 있겠네요. 다른 구현체를 참고해 다시 작성해 보셔도 될 듯합니다

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