[백준 2211] 네트워크 복구

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

2211번: 네트워크 복구

 

요구사항

1번 컴퓨터와 다른 컴퓨터를 최소 비용으로 연결하기

 

풀이

시작점이 주어졌으므로 다익스트라로 풀이한다

출력이 연결되는 간선이 어디에서 어디로 갔는가를 출력하는 것에서 고민을 했다ㅠㅠ

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
//#include <bits/stdc++.h>

using namespace std;

int n, m;
int startcity, endcity;
struct go {
	int x;
	int y;
};
vector<go> v[1001];
int dist[1001];
go ans[1001];
void solve() {
	for (int i = 1; i <= n; i++) {
		dist[i] = 987654321;
	}
	priority_queue<pair<int,int>> q;
	dist[1] = 0;
	q.push({ 0,1 });
	while (!q.empty()) {
		int nowcity = q.top().second;
		int nowdist = -q.top().first;
		q.pop();
		for (int i = 0; i < v[nowcity].size(); i++) {
			int next = v[nowcity][i].x;
			int nextdist = v[nowcity][i].y;
			if (dist[next] > nowdist + nextdist) {
		//		cout << "nowcity" << nowcity << " " << next << endl;
				dist[next] = nowdist + nextdist;
				q.push({ -dist[next],next });
			//	ans.push_back({ nowcity,next });
				ans[next].x = nowcity;
				ans[next].y = next;
			}
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		v[x].push_back({ y,z });
		v[y].push_back({ x,z });
	}
	solve();
	cout << n - 1 << endl;
	for (int i = 2; i <= n; i++) {
		printf("%d %d\n", ans[i].x, ans[i].y);
	}

}