다익스트라1 [BOJ] 11779번: 최소비용 구하기 2 https://www.acmicpc.net/problem/11779 다익스트라를 구현하는데 경로를 저장해야 한다. 추적방법 trace 배열을 선언한다. 다익스트라 알고리즘에서 거리 업데이트하는 부분에 trace[nxt.idx] = now.idx로 지정한다. 도착 지점부터 trace 배열을 돌면서 t = trace[t]를 통해 노드 A로 오기 전 노드로 t를 변경한다. #include using namespace std; struct Edg { int idx, fair; Edg(int i, int f) : idx(i), fair(f) {} bool operator nxt.fair + now.fair) { dist[nxt.idx] = nxt.fair + now.fair; trace[nxt.idx] = now.. 2018. 8. 7. 이전 1 다음