5719번 - 거의 최단 경로
저는 디익스트라 1번 -> 역추적으로 간선들 제거 -> 디익스트라 1번
으로 풀었습니다.
역추적으로 간선들 제거하는 과정에서 동일한 정점을 두번 큐에 넣지 마세요. vector<bool>로 처리해주세요
간선은 제거하되 동일한 정점을 계속해서 넣으면 BFS에서 무한루프가 돌면서 메모리 초과가납니다.
당신은 사람 한 명을 구했습니다
당신은 고수입니다
무한루프가 생기는 건 아니고 재방문을 막지 않으면 그냥 최악 시간 복잡도가 시간 제한을 넘는 게 맞습니다!최단 경로의 구조 상 무한 루프는 생길 수가 없을 것 같습니다.
와 존경합니다
선생님 정말 감사합니다 항상 좋은 일만 있었으면 좋겠습니다
뭘 하시든지 잘 풀리길 바랍니다
댓글을 작성하려면 로그인해야 합니다.
mym0404 5년 전 21
저는 디익스트라 1번 -> 역추적으로 간선들 제거 -> 디익스트라 1번
으로 풀었습니다.
역추적으로 간선들 제거하는 과정에서 동일한 정점을 두번 큐에 넣지 마세요. vector<bool>로 처리해주세요
간선은 제거하되 동일한 정점을 계속해서 넣으면 BFS에서 무한루프가 돌면서 메모리 초과가납니다.