백준 5719 거의 최단경로

백준 5719 거의 최단경로

난이도 꽤 있다고 생각함.

https://www.acmicpc.net/problem/5719

다익스트라를 이용하여 최단경로를 저장해나가는데 pred 벡터에 이전 경로를 갱신해준다.

그리고 이전경로를 모두 탐색해 그 경로를 재귀적으로 접근하여 -~ 사용할 수 없는 간선으로 만든다.

그리고 다시 다익스트라를 활용한다.

그러면 거의 최단경로가 나온다.

개념적으로 와닿지만, 

pred 를 어떻게 벡터로 만들고, ... 그리고 어떻게 삭제하는가... 에 대해서 생각하는데 시간이 많이 걸린 문제였다. 여기서 아마 구현능력과 논리력이 갈리었을거라 생각한ㄷㅏ

리저널,, 문제였는데 어렵긴 어려운것 같다. 난 제한 시간내에 못풀었다 100% ㅋㅋㅋ.

이 문제로 인해 느낀점은, pred 벡터에 target으로 갈 수 있는 여러 경로~ 그러니까 6으로 가는데에 최단경로로서 이전 vertex가 2 , 3 등이 존재할 수 있을 때 어떻게 pred에 동시에 저장해줄 것이냐... 가 질문일것이다. 이런것을 잘 구현해야할 것같다. 난 벡터로 했다.

소스보기

https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/5719.cc