다익스트라 (1) 썸네일형 리스트형 [C++] 최소비용 구하기2 백준 11779번 다익스트라로 풀어본 최소비용 구하기 문제 가장 기본적인 다익스트라는 거리(비용)만 구하는데 경로까지 구해야 하는 문제였다 경로를 우선순위큐에 vector로 다 넣어주었는데 간단하게 풀고싶어서 그렇게 풀긴 했지만 좋은 풀이는 아닌 것 같다 메모리를 줄이기 위해 다른 풀이가 있는지 찾아보았더니 특정점 a를 가기 위한 최적 경로가 b를 통해서라면 route[a] = b와 같이 저장해서 쓰는 방법이 있었다 이렇게하면 모든 경로를 벡터로 갖지 않아도 역추적이 가능하다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 .. 이전 1 다음
