1238 파티

정점의 개수가 N=1000으로 플로이드가 가까스로 통과하게 된다. 단순한 계산은 1억번해도 1초 미만이다

시간을 줄일 수 있는 방법은 없나?

플로이드를 사용한 이유는 짧은 코드로 모든 정점간의 최단경로를 구할 수 있었기 때문이다. 구하고자 하는 것을 명확히 한다면 다른 알고리즘으로도 해결할 수 있다는 것이다

이전에 사용했던 다익스트라는 시작점이 하나로 우선순위 큐를 사용했을 때 시간복잡도는 O(NlgE)다. 따라서 모든 정점에 대해서 살펴본다면 O(N^2*lgE)로 거의 N^2에 해결할 수 있어서 시간을 단축시킬 수 있다

 

문제: https://www.acmicpc.net/problem/1238

플로이드: https://github.com/surinoel/boj/blob/master/1238_floyd.cpp

다익스트라: https://github.com/surinoel/boj/blob/master/1238_dijkstra.cpp