모든 쌍의 개수부터 O(n2)이기 때문에 시간 내에 그 정도의 정보를 저장하는 것 자체가 불가능합니다.
쿼리 10만 개를 주고 각 쿼리마다 어떤 한 쌍을 계산하라는 문제를 낼 수는 있겠지만, 그런 문제가 여기 있는지는 모르겠습니다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호
hoon8810 6년 전
문제를 풀다가.. 답답해서 글 남겨봅니다.
정점수가 최대 10만개인
유향그래프가 주어지고 모든 정점쌍에 대한
최단경로를 구하라는 문제인데..
플로이드 워셜은 당연 안되고
다익스트라 정점갯수만큼 돌리는것도 결국 n2 이 되니까 안되고
유향그래프라 트리로 만들수도 없어서 LCA도 아닌것 같은데
정점수가 많은 그래프에서 모든 쌍의 최단경로를 구해보신분 계신가요?