백준 5719 거의 최단경로

백준 5719 거의 최단경로 난이도 꽤 있다고 생각함.https://www.acmicpc.net/problem/5719 다익스트라를 이용하여 최단경로를 저장해나가는데 pred 벡터에 이전 경로를 갱신해준다.그리고 이전경로를 모두 탐색해 그 경로를 재귀적으로 접근하여 -~ 사용할 수 없는 간선으로 만든다.그리고 다시 다익스트라를 활용한다. 그러면 거의 최단경로가 나온다. 개념적으로 와닿지만, pred 를 어떻게 벡터로 만들고, ... 그리고 어떻게 삭제하는가... 에 대해서 생각하는데 시간이 많이 걸린 문제였다. 여기서 아마 구현능력과 논리력이 갈리었을거라 생각한ㄷㅏ 리저널,, 문제였는데 어렵긴 어려운것 같다. 난 제한 시간내에 못풀었다 100% ㅋㅋㅋ. 이 문제로 인해 느낀점은, pred 벡터에 targ..
알고리즘 문제/graph 2018. 2. 23. 05:11
1