[백준/C++] 10282번: 해킹

방법

다익스트라 알고리즘

• 첫째 줄에 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다
• 이어서 d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다

① b --s(가중치)--> a 형태로 그래프 만들고, c를 시작점으로 다익스트라 수행

② 감염된 컴퓨터 수 : dist[1] ~ dist[n] 중 갱신된 dist[i]의 개수 (즉, INF가 아닌 것 찾아주면 됨)

③ 마지막 컴퓨터 감염될 때까지 걸리는 시간 : ②에 속하는 dist[i] 중 최댓값

코드

#include<bits/stdc++.h>
#define INF 987654321
using namespace std;

struct info {
	int n, w;
	info() {};
	info(int n, int w) :n(n), w(w) {};

	bool operator<(const info i) const {
		return w > i.w;
	}
};

int t, n, d, c;
vector<info> g[10001];
int dist[10001];
bool check[10001];

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

	cin >> t;
	while (t--) {
		cin >> n >> d >> c;
		for (int i = 0; i <= n; i++) {
			dist[i] = INF;
			check[i] = false;
			g[i].clear();
		}
		for (int i = 0, a, b, s; i < d; i++) {
			cin >> a >> b >> s;	// b 감염되면, s초 후 a도 감염
			g[b].push_back(info(a, s));
		}

		priority_queue<info> pq;
		pq.push(info(c, 0));
		dist[c] = 0;
		while (!pq.empty()) {
			info cur = pq.top();
			pq.pop();
			if (check[cur.n]) continue;
			check[cur.n] = true;
			for (int i = 0; i < g[cur.n].size(); i++) {
				int nxt_n = g[cur.n][i].n;
				int nxt_w = g[cur.n][i].w;
				if (dist[nxt_n] > dist[cur.n] + nxt_w) {
					dist[nxt_n] = dist[cur.n] + nxt_w;
					pq.push(info(nxt_n, dist[nxt_n]));
				}
			}
		}

		int cnt = 0;
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			if (dist[i] == INF) continue;
			if (dist[i] != INF) cnt++;
			if (ans < dist[i]) ans = dist[i];
		}
		cout << cnt << " " << ans << "\n";
	}

	return 0;
}