[백준OJ] 10282번 해킹

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

10282번: 해킹

---

 

풀이

다익스트라 알고리즘을 이용하여, 해킹을 시작한 컴퓨터로부터 의존성이 존재하는 컴퓨터들까지의 최단거리를 모두 구한 뒤, 도달할 수 있는 컴퓨터의 개수(코드에서 dist의 값이 INF가 아닌것들은 도달 할 수 있다는 의미)를 세어주면서, 모두 감염이 되는 시간은, 가장 마지막으로 감염이된 컴퓨터의 시간이 된다.

 

시간복잡도

우선순위큐를 이용한 다익스트라 알고리즘의 시간복잡도는 O(DlogN)이 된다.

 

반응형

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define MAX	10001
#define INF 987654321
using namespace std;

typedef pair<int, int> pii;

int tc, n, d, c;
vector<pii> maze[MAX];

void init() {
	for (int i = 0; i < MAX; i++) {
		maze[i].clear();
	}
}

void make_graph() {
	for (int i = 0; i < d; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		maze[v].push_back({ u,w });
	}
}

pii dijk() {
	vector<int> dist(n + 2,INF);
	priority_queue<pii> q;
	pii ret = { 0,0 };
	dist[c] = 0;
	q.push({ 0,c });
	while (!q.empty()) {
		int now = q.top().second;
		int now_dist = -q.top().first;
		q.pop();
		if (now_dist > dist[now]) continue;

		for (pii next : maze[now]) {
			int next_node = next.first;
			int next_cost = next.second+now_dist;
			if (next_cost < dist[next_node]) {
				dist[next_node] = next_cost;
				q.push({ -next_cost,next_node });
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (dist[i] != INF) {
			ret.first++;
			ret.second = max(ret.second, dist[i]);
		}
	}
	return ret;
}

int main() {
	cin >> tc;
	while (tc--) {
		init();
		cin >> n >> d >> c;
		make_graph();
		pii ret = dijk();
		cout << ret.first<<" "<<ret.second << "\n";
	}

	return 0;
}