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

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

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

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

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

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