(BOJ) 10282 해킹

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

 

문제 풀이:

"단방향"으로 감염됨! a,b,s이면 b->a 감염시키고 a->b 감염 못 시킴 

처음 감염된 컴퓨터 기준으로 다익스트라 돌림

그리고 1~N까지 포문 돌리면서 dist[i]!=inf (감염되지 않지 않았다면) cnt++;

dist 중에 가장 큰 수가 감염되기까지 걸리는 시간이다.

 

소스 코드:

typedef pair<int, int> P;
vector<vector<P>> v;
int tc, dist[10001], n, m, k;
bool visit[10001];
priority_queue<P, vector<P>, greater<P>> pq;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> tc;
	while (tc--) {
		cin >> n >> m >> k;
		fill(dist, dist + n + 1, inf);
		memset(visit, false, sizeof(visit));
		v.clear();
		v.resize(n + 1);

		for (int i = 0; i < m; i++) {
			int q, w, e;
			cin >> q >> w >> e;
			v[w].push_back({ q,e });
		}
		dist[k] = 0;

		while (!pq.empty()) pq.pop();

		pq.push({ 0,k });

		while (!pq.empty()) {
			int cur;
			do {
				cur = pq.top().second;
				pq.pop();
			} while (!pq.empty() && visit[cur]);
			if (visit[cur]) break;
			visit[cur] = true;

			for (int i = 0; i < v[cur].size(); i++) {
				if (dist[v[cur][i].first] > dist[cur] + v[cur][i].second) {
					dist[v[cur][i].first] = dist[cur] + v[cur][i].second;
					pq.push({ dist[v[cur][i].first],v[cur][i].first });
				}
			}
		}
		int res = 0;
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			if (dist[i] != inf) {
				cnt++;
				res = max(res, dist[i]);
			}
		}
		cout << cnt << " " << res << '\n';
	}
	return 0;
}