C++ / 백준 / 10282 / 해킹

문제

 

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

10282번: 해킹

문제풀이

 

다익스트라 알고리즘으로 풀었다.

처음에 (N+1) * (N+1) 크기의 2차원 벡터로 풀어봤는데 메모리 초과가 떴다.

어느 부분이 문젠가 해서 검색해 보니 N의 최대 크기가 10,000이라 10,001 * 10,001 크기의 벡터를 선언할 수 있어 메모리 초과가 뜬것 같다.

그래서 이 부분을 pair가 섞인 벡터로 풀었더니 메모리 초과가 안 떴다.

 

세로가 N+1 크기의 가로는 비어있는 3차원 벡터를 선언하고 값을 입력받을 때마다 pair 형태로 입력한다.

 

그다음은 시작 노드를 인자로 받는 다익스트라 함수를 실행한다.

우선순위 큐를 이용하고 감염 시간이 적은 것이 top부분에 오도록 cmp함수를 짰다.

 

우선순위 큐가 빌 때까지 반복하면서 감염될 컴퓨터의 감염되기까지 걸리는 시간을 최소로 만들어준다.

마지막으로 log벡터를 탐색하면서 INF가 아닌 값을 발견할 경우 감염된 컴퓨터이므로, 감염된 컴퓨터 수를 늘려주고, 가장 늦게 감염된 컴퓨터의 감염시간을 저장한다.

코드

 

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

int N;
vector<vector<pair<int, int>>>network;

struct cmp {
	bool operator()(pair<int, int>a, pair<int, int>b) {
		return a.second > b.second;
	}
};

void Dijkstra(int start) {
	int idx(0), com(0), time(0), cnt(0), max_time(0), next(0), ntime(0);
	priority_queue<pair<int, int>,vector<pair<int, int>>, cmp>pq;

	vector<int>log(N + 1, INF);
	log[start] = 0;

	pq.push({ start,0 });

	while (!pq.empty()) {
		com = pq.top().first;
		time = pq.top().second;
		pq.pop();
		for (idx = 0; idx < network[com].size(); ++idx) {
			next = network[com][idx].first;
			ntime = network[com][idx].second;
			if (log[next] > time + ntime) {
				log[next] = time + ntime;
				pq.push({ next, log[next] });
			}
		}
	}

	for (idx = 1; idx <= N; ++idx) {
		if (log[idx] != INF) {
			cnt++;
			max_time = max(max_time, log[idx]);
		}
	}
	cout << cnt << " " << max_time << '\n';
}

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

	int T(0), D(0), C(0), C1(0), C2(0),S(0), idx(0);
	cin >> T;

	while (T--) {
		cin >> N >> D >> C;
		network = vector<vector<pair<int, int>>>(N+1);
		for (idx = 0; idx < D; ++idx) {
			cin >> C1 >> C2 >> S;
			network[C2].push_back({ C1,S });
		}
		Dijkstra(C);
	}
}