글 읽기 - SPFA 풀이가 통과됩니다.

다익스트라 쓰라고 만들어진 문제던데, 반례찾다 빡쳐서 SPFA에 영어 위키에서 본 Small Label First (SLF) technique를 사용해서 제출했는데 맞았습니다.

여전히 최악의 경우가 O(V * E)인데 통과되어서 질문합니다.

제출해서 맞은 코드 링크

SPFA 영문 위키 링크

데이터 추가 요청을 할 때는 되도록이면 데이터를 만들어 주세요.

아무튼 저도 C++로 똑같은 알고리즘을 구현해봤습니다.

제가 아는 건 이것의 시간복잡도가 최악의 경우 O(VE)라는 것 뿐이여서..

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

Baekjoon Online Judge