[BOJ 2211] 네트워크 복구

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

처음 문제 조건 1번을 읽고 2번을 읽은 후, MST를 하는 과정에서 다익스트라로 제한을 걸면서 MST를 만들면 되는줄 알았는데 개 망 ... 

해매다가 Q&A 에서 본 것을 통해 그냥 단순 다익스트라로 풀 수 있다고 알게 되었다 (근데 아직 정확히 와닿지는 않음 ..)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <stdio.h>
 
#define INF 1e9
typedef long long ll;
using namespace std;
 
int n,m,dist[1111],parent[1111];
bool visit[1111];
vector<vector<pair<int,int>>> v;
vector<pair<int,pair<int,int>>> vt;
vector<pair<int,int>> ans;
void solve(){
    for(int i=0;i<=n;i++){
        dist[i] =INF;
        parent[i] = -1;
    }
    dist[1] = 0;
    parent[1] = 1;
    priority_queue<pair<int,int>> q;
    q.push({0,1});
    
    while(!q.empty()){
        int x= q.top().second;
        q.pop();
        
        if(visit[x])continue;
        visit[x] = true;
        
        for(int i=0;i<v[x].size();i++){
            int y = v[x][i].first;
            if(dist[y] > dist[x] +v[x][i].second){
                dist[y] = dist[x] + v[x][i].second;
                q.push({-dist[y],y});
                parent[y] = x;
            }
        }
    }
}
 
int main(){
    memset(visit,false,sizeof(visit));
    cin >> n>>m;
    v.resize(n+1);
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >>b>>c;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
    solve();
    int ans =0;
    for(int i=2;i<=n;i++){
        if(parent[i] != -1){
            ans ++;
        }
    }
    cout << ans <<endl;
    for(int i=2;i<=n;i++){
        if(parent[i] != -1){
            cout << i << " " << parent[i] <<endl;
        }
    }
    return 0;
}
 

+추가) 정확히 안 와닿아서 풀이를 샀다