hoon8810   3년 전

문제를 풀다가.. 답답해서 글 남겨봅니다. 

정점수가 최대 10만개인

유향그래프가 주어지고 모든 정점쌍에 대한

최단경로를 구하라는 문제인데..

플로이드 워셜은 당연 안되고

다익스트라 정점갯수만큼 돌리는것도 결국 n이 되니까 안되고

유향그래프라 트리로 만들수도 없어서 LCA도 아닌것 같은데

정점수가 많은 그래프에서 모든 쌍의 최단경로를 구해보신분 계신가요?

jh05013   3년 전

모든 쌍의 개수부터 O(n2)이기 때문에 시간 내에 그 정도의 정보를 저장하는 것 자체가 불가능합니다.

쿼리 10만 개를 주고 각 쿼리마다 어떤 한 쌍을 계산하라는 문제를 낼 수는 있겠지만, 그런 문제가 여기 있는지는 모르겠습니다.

hoon8810   3년 전

감사합니다. 문제의 목표는 모든 쌍의 최단거리의 합을 구하는건데 흠.. 문제접근이 잘못된건지. 더 고민해봐야겠네요.

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