글 읽기 - 플로이드 와샬로는 처리가 불가능한가요?

플로이드-와샬로 처리(오답)

데이크스트라로 처리(정답)

노드의 수가 작기 때문에 한번 플로이드 와샬로 처리해봤습니다만

예제는 잘 출력하나 50%에서 계속 오답처리됩니다.

플로이드 와샬로 처리한 코드의 경우에는 일반적인 플로이드 와샬로 처리하였고

특이한 점이라면 백트래킹을 위해 visited을 만들고, 여기에 최소값 갱신시 최근 방문 노드를 입력해놓았습니다.

알고리즘 처리 후 while문으로 visited을 하나씩 거슬러 올라가면서 방문한 내역을 res에 추가했구요.

만약 방문한 내역이 없었다면, 0 -> 마지막노드까지 직접 방문이 가능한지 확인해보고 있으면 이를 정답에 출력하도록 처리했습니다.

정답은 데이크스트라로 맞추긴 했으나, 플로이드와샬로는 처리가 불가능한건지 궁금합니다.

혹시 테스트케이스중에

1 2 1

1 2 3

1 2 2

이렇게 중복돼서 주어지는것이 있지 않을까요

그럼 거리갱신할떄 기존값보다 작아야지 갱신가능하게 해야합니다

다익스트라는 어차피 이래도 정보가 다 저장되니까 가능한데

플로이드 틀리는거면 중복이 주어질 가능성이 있어요

그럼 문제 논리상 잘 안 맞는거 같습니다.

a와 b는 측근이자, 지인이라는 논리가 좀 이상한거 같아요

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

Baekjoon Online Judge