다익스트라경로1

• 

  [C++] 백준 - 11779 최소비용구하기2 (다익스트라) 1. 문제 2. 입출력 및 예제 3. 문제 해설 백준 - 1916 최소비용 구하기 문제와 비슷한 문제이다. 하지만 추가된 것은 몇 개의 노드를 거치면서 왔는 지에 대한 정보와 지나온 path에 대한 정보도 출력을 해야한다는 것이다. 처음에 예제 답안을 살펴보면 경로가 1 3 5로 나와있는 것을 확인할 수 있다. 하지만 위의 그래프를 그려보면 1 3 5 뿐만 아니라 1 4 5도 된다는 것을 알 수 있다. 그리고 경로에 대한 제약사항은 존재하지 않는다. 따라서 이 문제는 도달할 수 있는 경로가 여러가지일 경우에는 그냥 아무거나 출력하면 되는 문제였다. 여태까지 많은 경로를 기억했다가 출력하는 문제들을 풀어본 결과 경로를 기억하는 문제들은 대게 그 경로에 추가되는 로직이 있기 마련이다. 또한 위의 문제는 다익.. c++/알고리즘 2023. 2. 15.