[백준BOJ] 2211 네트워크 복구

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

2211번: 네트워크 복구

 

---

문제 설명이 너무 길고 약간 복잡하다. 그러나 이해만 잘하면 쉽게 풀 수 있는 문제이다.

최소한의 경로의 갯수 , 최소한의 경로의 합

을 만족시키기 위해서는 N개의 정점이 있을떄 N-1개의 간선을 사용하면 되고

N-1개의 간선의 합이 최소한의 경로가 되면 된다.

 

---

전체코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

#define MAX_N 1001
vector<pair<int,int>> vec[MAX_N];

class PQItem {
public:
     int n;
     int cost;
     PQItem(int n, int cost ) {
          this->n = n;
          this->cost = cost;
     }
     bool operator > (const PQItem & b) const {
          return this->cost > b.cost;
     }
};
priority_queue<PQItem, vector<PQItem>, greater<> > pq;

int dist[MAX_N];
int connect[MAX_N];
int connectCnt = 0;

void dijstra() {
     pq.push(PQItem(1, 0));
     dist[1] = 0;
     while (!pq.empty()) {
          PQItem top = pq.top(); pq.pop();
          int n = top.n;
          int cost = top.cost;
          if (dist[n] < cost) continue;
          for (int i = 0; i < vec[n].size(); i++) {
               int nextCost = vec[n][i].second + cost;
               if (dist[vec[n][i].first] > nextCost) {
                    dist[vec[n][i].first] = nextCost;
                    connect[vec[n][i].first] = n;
                    pq.push(PQItem(vec[n][i].first, nextCost));
               }
          }
     }
}


int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int N, M;
     cin >> N >> M;
     for (int i = 0; i <= N; i++) {
          dist[i] = 1e9;
     }
     for (int i = 0; i < M; i++) {
          int a, b, w; cin >> a >> b >> w;
          vec[a].push_back({b,w});
          vec[b].push_back({a,w});
     }
     dijstra();
     cout << N - 1 << "\n";
     for (int i = 2; i <= N; i++) {
         cout << i << " " << connect[i] << "\n";
     }
}