ch6403   2년 전

DFS 로 풀 수 있겠지 하면서 풀었습니다..

1시간 동안 9%에서 맞왜틀 외치던 저에게 깨달음을 준 반례입니다,,

A  -> C -> D 로 가는 것이 최단일 때,

A -> B -> C 로 탐색하면서 C를 visited 처리해서 D에 도달 못할 수도 있단 것을 알게 됐네요.

최단거리 재야할 때는 BFS 쓰거나 다익스트라/플로이드 쓰는걸로

반례

5 15 5
2 4 5 20 3
1 2 6
2 3 7
3 4 9
1 3 2
1 5 14

---

정답 : 34

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