1753번 - 최단경로
글 읽기 - 반례 좀 부탁드립니다 + 시도해 본 예시들 (acmicpc.net)
(다익스트라로 풀어야함을 알고 있지만 BFS로 푸는 것을 시도하였습니다)
BFS로 코드를 작성했는데, 게시판의 글 맨 위 반례들은 통과하지만 막상 돌리면 틀립니다...ㅠ
다익스트라와는 다르게 BFS에서는 노드가 갱신되면 갱신된 시점의 노드에서부터 다시 연산을 해야 한다고 하는데,
혹시 이 코드의 반례가 있을까요...?
돌려보진 않았지맞 대충 다음 반례가 있을 것 같습니다.
4 4
1
1 2 10
1 3 1
3 2 1
2 4 1
와.. 정말 답답했는데 완전 감사합니다!!!! ㅠㅠㅠㅠㅠㅠ
댓글을 작성하려면 로그인해야 합니다.
miramira227 1년 전
글 읽기 - 반례 좀 부탁드립니다 + 시도해 본 예시들 (acmicpc.net)
(다익스트라로 풀어야함을 알고 있지만 BFS로 푸는 것을 시도하였습니다)
BFS로 코드를 작성했는데, 게시판의 글 맨 위 반례들은 통과하지만 막상 돌리면 틀립니다...ㅠ
다익스트라와는 다르게 BFS에서는 노드가 갱신되면 갱신된 시점의 노드에서부터 다시 연산을 해야 한다고 하는데,
혹시 이 코드의 반례가 있을까요...?