백준 2211 : 네트워크 복구

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

처음에 최소스패닝트리(MST) 문제인지 헷갈려서 삽질을 했다.

그러나 위의 (2)번 조건에 의해 결국 다익스트라로 해결해야 한다.

모든 컴퓨터들이 1번 슈퍼컴퓨터와의 최소경로를 만족해야한다. 따라서 1번을 기준으로 다익스트라를 해주고

각 컴퓨터들에 저장된 이전 정점 정보를 가져와 연결하면 된다.

Com 구조체에 현재 거리 뿐만 아니라 이전 정점의 정보까지 저장해야 한다.

struct com{

int idx, dist = INF, post = 0;

};

다익스트라를 돌면서 최소 거리를 갱신해줄 때 post값도 갱신해주면 된다.

for(현재 정점과 연결된 모든정점 탐색){

if(다음 정점의 거리 > 현재정점까지 거리 + 간선의 가중치){

//최소거리 갱신

1. 다음정점의 거리 = 현재정점까지거리 + 간선의 가중치

2. 다음정점의 post 값 = 현재정점의 인덱스

3. 우선순위 큐에 다음정점 저장

}

}

이처럼 post를 통해 연결된 정점을 저장해주면 각 정점에서 post가 0이될때까지 탐색을 통해 최소경로를 모두 탐색할 수 있다.

벡터에 경로를 넣고 visited[][] 를 통해 이미 넣은경로를 중복해서 넣지않도록 해주었다.

결국 다익스트라를 통해

모든 컴퓨터가 1번컴퓨터와 최단경로로 연결되어 있으므로 1번 조건의 스패닝트리는 무조건 만족한다.

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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

#include <iostream> #include <vector> #include <queue> #define MAX 1001 #define INF 2000000000 using namespace std; int n, m; struct Com{ int idx, dist = INF, post = 0; vector<pair<int, int>> next; bool operator < (const Com &c) const { return dist > c.dist; } }; Com com[MAX]; bool visited[MAX][MAX]; vector<pair<int, int>> recovered; void traceNetwork(){ for(int i = 1; i <= n; i++){ Com cur = com[i]; while(cur.post != 0){ if(!visited[cur.idx][cur.post]){ visited[cur.idx][cur.post] = true; visited[cur.post][cur.idx] = true; recovered.push_back(make_pair(cur.idx, cur.post)); } cur = com[cur.post]; } } } void netPrint(){ cout << recovered.size() << '\n'; for(pair<int, int> pa : recovered){ cout << pa.first << " " << pa.second << '\n'; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i = 1; i <= n; i++){ com[i].idx = i; } while(m--){ int i, j, w; cin >> i >> j >> w; com[i].next.push_back(make_pair(w, j)); com[j].next.push_back(make_pair(w, i)); } //dijkstra algorithm priority_queue<Com> pq; com[1].dist = 0; pq.push(com[1]); while(!pq.empty()){ Com curCom = pq.top(); pq.pop(); for(pair<int, int> pa : curCom.next){ if(com[pa.second].dist > curCom.dist + pa.first){ com[pa.second].dist = curCom.dist + pa.first; com[pa.second].post = curCom.idx; pq.push(com[pa.second]); } } } traceNetwork(); netPrint(); return 0; }