1848번 - 동굴 탐험
시작점 (1번 노드) 에서 에지로 연결되는 노드들에 대해 모두 dijkstra를 돌렸습니다.
각 다익스트라 dist 배열 마다 1번 노드에 직접 연결된 다른 노드로 가는 최단거리가 INF가 아니라면
길이 있다는 것이고, 이에 따라
1 -> 1번에 연결된 노드 -> 1번에 연결된 다른 노드 -> 1
경로 중 min값이 최소가 됩니다.
매 다익스트라 마다 각 상황의 최소값을 저장하여 최종 제일 작은 값을 뽑았을 때가 답이라고 생각했습니다.
예제는 맞게 돌아가는데 왜 틀릴까요?
댓글을 작성하려면 로그인해야 합니다.
oyj0594 7년 전
시작점 (1번 노드) 에서 에지로 연결되는 노드들에 대해 모두 dijkstra를 돌렸습니다.
각 다익스트라 dist 배열 마다 1번 노드에 직접 연결된 다른 노드로 가는 최단거리가 INF가 아니라면
길이 있다는 것이고, 이에 따라
1 -> 1번에 연결된 노드 -> 1번에 연결된 다른 노드 -> 1
경로 중 min값이 최소가 됩니다.
매 다익스트라 마다 각 상황의 최소값을 저장하여 최종 제일 작은 값을 뽑았을 때가 답이라고 생각했습니다.
예제는 맞게 돌아가는데 왜 틀릴까요?