BOJ 10282 해킹

www.acmicpc.net/problem/10282

10282번: 해킹

 

컴퓨터 a가 b를 의존한다면 b컴퓨터가 감염되었을 경우 c초 뒤에 a컴퓨터도 감염된다.

결국 모든 노드에서 한 방향으로 가는 최단거리를 안다면 쉽게 풀리는 문제였다.

첫 시작점에서 다익스트라를 쓰고 INF가 아닌 노드들을 카운트해주고 그 거리 값 중에서 가장 긴 거리 값이 정답이 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int INF = 1e9;
int n, d, c, a, b, s, tc;
vector<vector<pair<int, int>>> ar;

vector<int> dijkstra(int s) {
	priority_queue<pair<int, int>> pq;
	vector<int> d(n, INF);
	d[s] = 0;
	pq.push({ 0,s });

	while (!pq.empty()) {
		int cur = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();
		if (d[cur] < cost) continue;
		for (auto i : ar[cur]) {
			int nc = i.second + cost;
			if (nc < d[i.first]) {
				d[i.first] = nc;
				pq.push({ -nc,i.first });
			}
		}
	}

	return d;
}

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

	cin >> tc;
	while (tc--) {
		int cnt = 0, ans = 0;

		cin >> n >> d >> c;
		ar.resize(n);

		for (int i = 0; i < d; ++i) {
			cin >> a >> b >> s;
			ar[b - 1].push_back({ a - 1,s });
		}

		vector<int> d = dijkstra(c - 1);

		for (int i : d) {
			if (i == INF) continue;
			cnt++;
			if (i > ans) ans = i;
		}

		cout << cnt << ' ' << ans << '\n';
		ar.clear();
	}

	return 0;
}

 

근데 INF가 아닌 가장 긴 거리값이 정답이 되는 건지 궁금했는데 생각해보니

그 거리를 지나는 동안 다른 노드들은 이미 감염이 완료되어서 그렇다.