QuqqU   4년 전

저는 다익스트라로 풀었는데....


1->2->4   1->3->4  5->4 에서 위상정렬은 12354가 되고

위상정렬하고 dp를 씌운다해도,

앞쪽 정점이 현재 정점과 관련이 있는지 없는지 확인을 해야되야하니

n^2아닌가요??


위상정렬로 풀은게 다익스트라보다 좋은점이뭔가요?

jh05013   4년 전

각 노드마다 인접한 노드를 갱신해 주면서 풀면 앞쪽 노드의 영향이 이미 계산된 채로 시간을 바로 계산할 수 있습니다.

QuqqU   4년 전

그게 다익스트라랑 비교해서 좋은 점이 뭔가요??

다익스트라도 각노드마다 인접한 노드를 업데이트 시켜주지 않나요??

jh05013   4년 전

코드를 보니 이런 형태의 입력에서 O(N2+K)이 걸릴 것 같네요. (O(NK)까지 갈 지는 잘 모르겠습니다.)

rdd6584   3년 전

저도 다익으로 풀었는데 질문자님 코드랑 알고리즘이 쪼금 다른거 같아서 질문 드립니다.

제가 c밖에 몰라서 코드가 잘 안읽혀서 그러는데, 어떤식으로 푸신건지좀 여쭤봐도 될까요?

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