[백준] 10282 해킹 (복습)

문제

최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.

최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

• 첫째 줄에 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다(1 ≤ n ≤ 10,000, 1 ≤ d ≤ 100,000, 1 ≤ c ≤ n).
• 이어서 d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다(1 ≤ a, b ≤ n, a ≠ b, 0 ≤ s ≤ 1,000). 이는 컴퓨터 a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다.

각 테스트 케이스에서 같은 의존성 (a, b)가 두 번 이상 존재하지 않는다.

 

각 정점이 컴퓨터일때, a컴퓨터가 감염되면 s시간 후 b컴퓨터가 감염됩니다.

a 컴퓨터가 감염되는경우 c컴퓨터가 감염될 때까지 걸리는 시간은 최소시간이 되어야합니다.

다익스트라알고리즘을 사용합니다.

#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int> pi;
vector<pi>com[10001];
int v[10001], n, d, c;
int INTMAX = 10000001;
pi bfs(int start) {
	fill(v + 1, v + 1 + n, INTMAX);
	priority_queue<pi, vector<pi>, greater<pi>> pq;
	pq.push({0,start});
	v[start] = 0;
	int num = 1;
	while (!pq.empty()) {
		auto [dist,top] = pq.top(); pq.pop();
		for (auto [nxt,cost] : com[top]) {
			if (v[nxt] == INTMAX && v[nxt] > dist + cost) {
				v[nxt] = dist + cost;
				num++;
				pq.push({ v[nxt],nxt });
			
			}
			else if (v[nxt] != INTMAX && v[nxt] > dist + cost) {
				v[nxt] =  (dist + cost);
				pq.push({ v[nxt],nxt });
		
			}
	
		}
	}
	int ans = -1;
	for (int i = 1; i <= n; i++) {
		if (v[i] != INTMAX)ans = max(ans, v[i]);
	}
	return { num, ans};
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int ti, a, b, s;
	cin >> ti;
	while (ti--) {
		cin >> n >> d >> c;
		for (int i = 1; i <= n; i++) {
			com[i].clear();
		}
		while (d--) {
			cin >> a >> b >> s;
			com[b].push_back({ a,s });
		}
		auto [num, tim] = bfs(c);
		cout << num << " " << tim << "\n";
	}
}