[백준 10282] 해킹

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

10282번: 해킹

#include <cstdio>
#include <list>
#include <cstring>
#include <queue>
int T;
int N, D, C;
int ans_cnt;
int ans_time;

struct _st
{
	int n;
	int t;
};
std::list<_st> L[10000 + 2];

struct COMP
{
	bool operator() (const _st &a, const _st &b) {
		return a.t > b.t;
	}
};

std::priority_queue<_st, std::vector<_st>, COMP> PQ;
int visited[10000 + 2];

void input()
{
	// init
	for (int i = 1; i <= 10001; i++) {
		L[i].clear();
	}
	ans_cnt = 0;
	ans_time = 0;

	scanf("%d %d %d", &N, &D, &C);
	for (int i = 0; i < D; i++) {
		int a = 0, b = 0, s = 0;
		scanf("%d %d %d", &a, &b, &s);
		L[b].push_back({ a, s });
	}
}


void hacking()
{
	// init
	PQ = {};
	for (int i = 1; i <= 10000; i++) {
		visited[i] = 0x7fffffff;
	}

	PQ.push({ C, 0 });
	visited[C] = 0;
	
	while (!PQ.empty()) {
		_st data = PQ.top();
		PQ.pop();

		for (_st conn : L[data.n]) {
			if (visited[conn.n] <= visited[data.n] + conn.t) continue;
			PQ.push({ conn.n, visited[data.n] + conn.t });
			visited[conn.n] = visited[data.n] + conn.t;
		}
	}
}


void output()
{
	for (int i = 1; i <= N; i++) {
		if (visited[i] == 0x7fffffff) continue;
		ans_cnt++;
		if (ans_time < visited[i]) ans_time = visited[i];
	}
}


int main()
{
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		input();
		hacking();
		output();
		printf("%d %d\n", ans_cnt, ans_time);
	}
	return 0;
}

1. b 컴퓨터가 감염되면 그로부터 s라는 시간 뒤에 a 컴퓨터가 감염되므로, b를 기준으로 정보를 가져와야 한다. 

따라서 리스트에 데이터를 push_back 할 때 a와 b를 바꾸어서 저장한다. 

2. 초기에 C 컴퓨터가 감염되어 바이러스가 퍼지는 과정은 기본적인 다익스트라 알고리즘을 사용한다. 방문 배열에 감염 시간을 기록하고, 현재 걸린 시간이 기존에 저장된 시간보다 짧으면 갱신해주는 방식이다. 

3. 만약 방문배열이 초기 0x7fffffff 값 그대로라면, 감염되지 않은 컴퓨터이다. 반면 값이 갱신되었다면 ans_cnt 값을 늘려주고, 만약 ans_time 값보다 방문 배열에 저장된 시간이 더 크면 ans_time을 갱신한다. 감염되기 위해 걸린 총 시간을 출력해야 하기 때문이다.