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

www.acmicpc.net/problem/2211

2211번: 네트워크 복구

1번 컴퓨터에서 각 컴퓨터까지 다익스트라로 최소 시간을 구하면서, 그때 come_from[there] = here을 통해 there에 어디서 왔는지 저장을 한다. 이렇게 만들어진 come_from을 통해 선을 구한다. 선은 pair(숫자 작은것, 숫자 큰 것)으로 나타냈으며 중복되지 않게 set에 저장하였다.

이 문제에서 주의해야 될 점은 다익스트라를 통해 스패닝 트리 구성이 가능하다는 것이다.

 

코드

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

int n, m;
vector<pair<int, int>> adj[1001];
set<pair<int, int>>::iterator it;

set<pair<int, int>> Solve(int start)
{
	vector<int> short_time(1001, 987654321); //각 지점까지 가는 최소 시간을 구한다
	priority_queue<pair<int, int>> pq;
	vector<int> come_from(1001, 0);

	short_time[start] = 0;
	pq.push(make_pair(-0, start));
	come_from[start] = 0;

	while (!pq.empty())
	{
		int here = pq.top().second;
		int here_cost = -pq.top().first;
		pq.pop();

		if (here_cost > short_time[here])
			continue;

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].second;
			int there_cost = here_cost + adj[here][i].first;

			if (there_cost < short_time[there])
			{
				short_time[there] = there_cost;
				pq.push(make_pair(-there_cost, there));
				come_from[there] = here;
			}
		}
	}

	set<pair<int, int>> result;
	for (int i = 1; i <= n; i++)
	{
		if (come_from[i] != 0)
		{
			int left = come_from[i];
			int right = i;
			pair<int, int> line = make_pair(min(left, right), max(left, right)); //연결된 선(숫자 작은것, 숫자 큰것)

			result.insert(line); //겹치지 않게 set에 저장
		}
	}

	return result;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;

		adj[a].push_back(make_pair(c, b));
		adj[b].push_back(make_pair(c, a));
	}

	set<pair<int, int>> result = Solve(1);

	cout << result.size() << "\n";

	for (it = result.begin(); it != result.end(); it++)
	{
		cout << (*it).first << " " << (*it).second << "\n";
	}


	return 0;
}