백준 - 2211번 : 네트워크 복구 (C++)

풀이 방법 : 다익스트라

처음엔 유니온 파인드로 접근 했으나 유니온 파인드로 하면 2번 조건을 고려하지 못한다는 것을 발견하게 되었다.
그래서 결국에는 슈퍼컴퓨터 즉 1번 컴퓨터에서 각 컴퓨터까지의 최단 거리를 고려하면서 구해야하므로
출발 지점에서 다른 모든 지점까지의 최단 거리를 구하는 다익스트라가 맞다고 생각했다.

다익스트라를 해주면서 각 지점까지의 최단 시간이 갱신될 때마다 그 지점까지 잇는 간선 정보를 갱신해주었다.

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

using namespace std;

int Time[1001] = {};
pair<int, int> Edge[1001] = {};

struct PosInfo
{
	int CurPos;
	int Time;
	vector<pair<int, int>> vecNetwork;
};

struct cmp
{
	bool operator() (const PosInfo& A, const PosInfo& B)
	{
		return A.Time > B.Time;
	}
};

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;

	vector<vector<pair<int, int>>> vecTime(N + 1);
	for (int i = 0; i < M; ++i)
	{
		int A, B, C;
		cin >> A >> B >> C;

		pair<int, int> Info;
		Info.first = B;
		Info.second = C;
		vecTime[A].push_back(Info);

		Info.first = A;
		vecTime[B].push_back(Info);
	}

	priority_queue<PosInfo, vector<PosInfo>, cmp> pqInfo;
	PosInfo Start;
	Start.CurPos = 1;
	Start.Time = 0;
	
	pqInfo.push(Start);

	for (int i = 2; i <= N; ++i)
	{
		Time[i] = 987654321;
	}

	vector<pair<int, int>> vecAnswer;

	while (!pqInfo.empty())
	{
		PosInfo Cur = pqInfo.top();
		pqInfo.pop();

		int Size = vecTime[Cur.CurPos].size();

		for (int i = 0; i < Size; ++i)
		{
			pair<int, int> Next = vecTime[Cur.CurPos][i];

			if (Time[Next.first] <= Cur.Time + Next.second)
				continue;

			pair<int, int> Ans(Cur.CurPos, Next.first);
			Edge[Next.first] = Ans;

			Time[Next.first] = Cur.Time + Next.second;
			PosInfo NInfo = Cur;
			NInfo.CurPos = Next.first;
			NInfo.Time += Next.second;

			pqInfo.push(NInfo);
		}
	}

	for (int i = 1; i <= N; ++i)
	{
		if (Edge[i].first != 0)
		{
			vecAnswer.push_back(Edge[i]);
		}
	}

	int Size = vecAnswer.size();
	cout << Size << '\n';
	
	for (int i = 0; i < Size; ++i)
	{
		cout << vecAnswer[i].first << ' ' << vecAnswer[i].second << '\n';
	}
}