[C++] 백준 10282번 - 해킹

오랜만에 도전해본 골드문제이다

앞서서 포스팅한 백준 1753번 - 최단경로를 활용하면 풀 수 있는 문제이다.

 

재사용을 위해 다익스트라 최단경로 알고리즘을 함수로 만들었고, 

문제에서 구하자고 하는 것이 무엇인지 파악하면 풀 수 있는 문제였던 것 같다.

특이했던 점은 a가 b컴퓨터를 의존하기 때문에 b가 감염되면 a도 감염된다는 점이다.

입력은 a >> b로 받지만, 그래프에 넣을때는 graph[b].push_back({ s, a }); 이런식으로 넣어주어야한다.

이 부분때문에 다익스트라 알고리즘을 잘못짰는지 맞왜틀하고 있었다. 

그리고 마지막에 초기화해주는 부분을 잊지 말자. 

#include <bits/stdc++.h>
#define endl '\n'
#define pii pair<int, int>
#define INF 987654321
using namespace std;

vector<pii> graph[10010];
int affected[10010];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int t;
int n, d, c;
int a, b, s;

void dijkstra(int start) {
	affected[start] = 0;
	pq.push({ affected[start], start});

	while (!pq.empty()) {
		int weight = pq.top().first;
		int current_vertex = pq.top().second;
		pq.pop();

		if (affected[current_vertex] < weight) continue;

		for (int i = 0; i < graph[current_vertex].size(); i++) {
			int next_weight = graph[current_vertex][i].first;
			int next_vertex = graph[current_vertex][i].second;

			if (affected[next_vertex] > weight + next_weight) {
				affected[next_vertex] = weight + next_weight;
				pq.push({ affected[next_vertex], next_vertex });
			}
		}
	}
}

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

	cin >> t;
	while (t--) {
		cin >> n >> d >> c;
		for (int i = 0; i < d; i++) {
			cin >> a >> b >> s;
			graph[b].push_back({ s, a });
		}
		for (int i = 1; i < n + 1; i++) {
			affected[i] = INF;
		}

		dijkstra(c);
		int num = 0;
		int total_time = 0;

		for (int i = 1; i < n + 1; i++) {
			if (affected[i] == INF) continue;
			num += 1;
		}
		for (int i = 1; i < n + 1; i++) {
			if (affected[i] == INF) continue;
			total_time = max(total_time, affected[i]);
		}

		cout << num << " " << total_time << endl;

		for (int i = 1; i < n + 1; i++) {
			graph[i].clear();
		}
		memset(affected, 0, sizeof(affected));
	}

	return 0;
}