[BOJ]2211번: 네트워크 복구

 

문제: https://www.acmicpc.net/problem/2211

---

다익스트라 문제입니다.

 

주어진 간선중에 1번 컴퓨터에서 모든 컴퓨터를 연결하되 최소비용 조건을 맞추려면

 

다익스트라의 최종 경로가 된 간선들만 뽑아내면 됩니다.

 

제가 해결한 방법은 다익스트라에서dist[] 배열을 pair<int,int>로 선언하여

first에는 길이 값을 담고, 길이가 더 짧을 만나 갱신될 때 마다

second값에 현재 나와 연결된 NODE 값을 저장해놓습니다.

 

그렇게 하면 최종적으로 dist[] 배열에 저장된 다익스트라의 (dist[i], dist[i].second) 모든 쌍이 정답입니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ2211.cc