2211번-네트워크 복구

문제

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

2211번: 네트워크 복구

---

접근방법

1) 접근 사고

 

2) 시간 복잡도

 

3) 배운 점

 

4) PS

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 1001;
const int INF = 987654321;
int parent[MAX];
int dist[MAX];
int n ,m;
vector<pair<int,int>> v[MAX];
 
int main(void)
{
    fastio;
    cin >> n >> m;
 
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({c,b});
        v[b].push_back({c,a});
    }
 
    fill(dist, dist + MAX, INF);
    auto dijkstra = [&](int start){
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
        dist[start] = 0;
        pq.push({0, start});
 
        while(!pq.empty())
        {
            int cur = pq.top().second;
            int cost = pq.top().first;
            pq.pop();
 
            if(dist[cur] < cost)
                continue;
 
            for(auto idx : v[cur])
            {
                int neighbor = idx.second;
                int neighborCost = cost + idx.first;
                if(dist[neighbor] > neighborCost)
                {
                    dist[neighbor] = neighborCost;
                    parent[neighbor] = cur;
                    pq.push({neighborCost, neighbor});
                }
            }
        }
            };
    dijkstra(1);
    cout << n - 1 << "\n"; //간선을 모두 이어서 통신하기 위해서는 최소 n - 1개가 필요하다.
    for(int i = 2; i <= n; i++)
    {
        //parent[i]: 컴퓨터가 출발한 지점
        //i: 컴퓨터의 도착 지점 간선을 의미
        cout << parent[i] << " " << i << "\n";
    }
}