BOJ 2211 네트워크 복구

사용한 알고리즘

다익스트라, DFS

알고리즘 설명

본래의 네트워크에서 슈퍼컴퓨터로 부터 다른 컴퓨터의 최단거리를 구해야한다.
먼저 컴퓨터들 간에 소요시간을 가중치로한 그래프를 구성한다.
이 뒤에 슈퍼컴퓨터를 시작노드 정하고 다익스트라 알고리즘을 적용한다.
다익스트라 알고리즘으로 슈퍼컴퓨터로 부터 각각 컴퓨터까지의 최단거리를 구할 수 있다.
슈퍼컴퓨터로 부터 DFS를 적용하여 최단거리를 만족하는 edge를 찾아내어 이를 vector에 저장한다.
저장된 edge들을 출력한다.

풀이

// baekjoon 2211 yechan
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int MAX_N=1001;
const int MAX_INF=2e9;

typedef pair<int,int> P;

int N, M, u, v, w, dist[MAX_N];
vector<P> adj[MAX_N];
vector<P> edge;
bool visited[MAX_N];

void dfs(int here) {
	visited[here]=true;
	for (int i=0; i<adj[here].size(); i++) {
		int nx = adj[here][i].first;
		int nw = adj[here][i].second;
		if (visited[nx]) continue;
		if (dist[nx] == dist[here] + nw) {
			edge.push_back(P(here,nx));
			dfs(nx);
		}
	}
}

int main() {
	scanf("%d%d", &N, &M);
	while (M--) {
		scanf("%d%d%d", &u, &v, &w);
		adj[u].push_back(P(v,w));
		adj[v].push_back(P(u,w));
	}

	fill(dist, dist+N+1, MAX_INF);
	dist[1] = 0;
	priority_queue<P, vector<P>, greater<P> > PQ;
	PQ.push(P(0, 1));
	while (!PQ.empty()) {
		int curr;
		do {
			curr = PQ.top().second;
			PQ.pop();
		} while (!PQ.empty() && visited[curr]);

		if (visited[curr]) break;
		visited[curr]=true;

		for (int i=0; i<adj[curr].size(); i++) {
			int nx = adj[curr][i].first;
			int nw = adj[curr][i].second;
			if (dist[nx] > dist[curr] + nw) {
				dist[nx] = dist[curr] + nw;
				PQ.push(P(dist[nx], nx));
			}
		}
	}

	fill(visited, visited+N+1, false);
	dfs(1);
	printf("%d\n", edge.size());
	for (int i=0; i<edge.size(); i++)
		printf("%d %d\n", edge[i].first, edge[i].second);
	return 0;
}