2개의 댓글이 있습니다.
-
-
safariworld -
음 dfs로 최단거리인 경로를 모두 찾아보셨다는 말인것같은데 주어진 모든경로를 본다면 O(v +e)로 해결하지 않으셨을것같습니다. (dfs에서 노드체크를 했다가 다시푸신다든지...)
힌트는 이미 N번노드까지의 최단거리를 구할때 특정노드까지의 최단거리 역시 구했다는겁니다
허접한 덧글입니다ㅠ
12년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
cliberty! ^-^
1번 도시에서 N번 도시로 가는 최단 경로를 다 찾는 문제인거 같은데요.
저는 BFS로 최단 거리를 구한 후
DFS로 1부터 N번까지의 거리가 최단거리인것들을 stl set에 삽입하는 방법을 생각했습니다.
물론 DFS는 리컬시브하게 구현하지 않았고 stl stack을 써서 구현을 했는데 TLE네요.
여튼 BFS와 DFS를 쓰는 문제는 아닌것 같네요.
힌트를 좀 주시면 감사하겠습니다.
12년 전