백준 2211번 : 네트워크 복구

문제 접근

---

한 주제에 대해 깊게 시도해보기 : 다익스트라편 시작이다. 경로를 저장하면 되는 골드2치고 생각보다 쉬운 문제였다.

 

 

문제 코드

---

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<pair<int,int>> adj[1001];
// 경로 저장하는 벡터
vector<int> via(1001, -1);
int N, M, A, B, C;

void circuit()
{
	vector<int> dist(1001, 10000001);
	priority_queue<pair<int,int>> q;
	
	dist[1] = 0;
	q.push(make_pair(0,1));
	
	while(!q.empty())
	{
		int here = q.top().second;
		int cost = -q.top().first;
		q.pop();
		
		if(dist[here] < cost)
			continue;
		
		for(int i=0; i<adj[here].size(); ++i)
		{
			int there = adj[here][i].second;
			int nextDist = cost + adj[here][i].first;
			
			if(nextDist < dist[there])
			{
				dist[there] = nextDist;
                // 갱신될 때마다 해당 부분의 부모 또한 갱신한다.
				via[there] = here;
				q.push(make_pair(-nextDist, there));
			}
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>N>>M;
	
	while(M--)
	{
		cin>>A>>B>>C;
		
		adj[A].push_back(make_pair(C,B));
		adj[B].push_back(make_pair(C,A));
	}
	
	circuit();
	
    // 모두 다 연결되어있는 상태였을테니, N 개의 정점을 이을려면 N-1 개의 간선이 필요하다.
	cout<<N-1<<'\n';
	
	for(int i=1; i<=N; ++i)
		if(via[i] != -1)
			cout<<i<<' '<<via[i]<<'\n';
}