BOJ : 10282 해킹

---

[BOJ 10282(G4) 리뷰]

단순히 몇대의 컴퓨터가 감염되는지 구하는 문제가 아닌, 감염이 가능한 모든 컴퓨터가 감염되는 최단 시간을 구해야 한다. 그러므로 이 문제를 해결하기 위해서는 다익스트라 알고리즘을 사용해야 한다.

시작 컴퓨터가 주어졌으니 시작컴퓨터로부터 다익스트라 알고리즘을 수행한다. 그 후에 시간이 기록된 DIST배열 전체를 확인하여, 거리가 갱신된 노드들이 감염된 컴퓨터의 숫자가 된다.
그리고 감염이 되는 시간은 항상 0보다크므로 DIST배열중 가장 큰 값이 모든 컴퓨터가 감염되는 최단경로가 될 것이다.

/*
	21.02.02
	BOJ : 10282 해킹 (https://www.acmicpc.net/problem/10282)
	다익스트라 알고리즘
*/
#include <bits/stdc++.h>

using namespace std;
#define pii pair<int,int>
#define val first
#define num second

int t;
int n, d, c;

vector <pii> adj[10001];
priority_queue <pii, vector<pii>, greater<pii>> pq;
int dist[10001];

void init() {
	for (int i = 1; i <= n; i++) {
		dist[i] = INT_MAX;
	}
}

void clear() {
	for (int i = 1; i <= n; i++) {
		adj[i].clear();
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> t;

	while (t--) {
		cin >> n >> d >> c;
		
		for (int i = 0; i < d; i++) {
			int a, b, s;
			cin >> a >> b >> s;
			adj[b].push_back({ s,a });
		}

		init();
		pq.push({ 0,c });

		while (!pq.empty()) {
			auto cur = pq.top(); pq.pop();

			if (dist[cur.num] < cur.val) continue;

			dist[cur.num] = cur.val;

			for (int i = 0; i < adj[cur.num].size(); i++) {
				auto nxt = adj[cur.num][i];

				int nDist = dist[cur.num] + nxt.val;
				if (dist[nxt.num] > nDist) {
					pq.push({ nDist,nxt.num });
				}
			}
		}

		int ans = 0;
		int mx = 0;
		for (int i = 1; i <= n; i++) {
			if (dist[i] != INT_MAX) {
				ans++;
				mx = max(mx, dist[i]);
			}
		}

		cout << ans << " " <<mx << '\n';
		clear();
	}
	
	return 0;
}