BLUE DOLPHIN

https://www.acmicpc.net/problem/1162 벽 부수기 문제와 비슷하다. 주어만 바뀐 느낌이고 트리 구조(?)에서 그래프로 바뀐 것 뿐이다. 도로를 포장하거나 안 하거나 두 가지 경우가 있으므로 그 두 가지 경우를 모두 확인해주면 된다. #include #include #include #include #include using namespace std; struct Edg { int idx, cnt; long long dst; Edg(int idx, long long dst) : idx(idx), dst(dst) {} Edg(int idx, long long dst, int cnt) : idx(idx), dst(dst), cnt(cnt) {} bool operator nxt.dst ..

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..