ssilb4   8달 전

플로이드 워셜 알고리즘 썼는데 시간초과 뜨네요 ㅠ


다른 알고리즘을 써야하나요?


아니면 다른 방법이 있나요?

yukariko   8달 전

플로이드는 d[i][k] 가 갈 수 없는 경로일 경우를 처리하지않고 미리 다음 i로 가는것으로 최적화가 가능합니다.

이 경우에도 그 최적화를 통해 시간안에 해결이 되네요

아마 정해는 다익스트라 일것같습니다.

ssilb4   8달 전

감사합니다

덕분에 쉽게 해결했네요 ㅎㅎ

제가 알고리즘을 잘 몰라서 그런데...

지나간 경로를 출력하려면 다익스트라 보다는 플로이드가 쓰라는 걸 본 것 같은데..

상관없는 건가요?

yukariko   8달 전

네 둘 다 중간 경로를 출력할 수 있습니다.

ssilb4   8달 전

아..그렇군요

답변 감사드립니다.

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