백준 10282 c++ "해킹" -[PlusUltraCode]

 

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

 

[필자 사고]

 

다익스트라 알고리즘을 이용하면 쉽게 해결할 수 있는 문제이다.

 

이 문제의 핵심은 관계에 있다.

 

아무 생각없이 a->b로 그래프를 연결하는게 아닌 b가 감염되면 a는 몇초뒤에 감염된다 라고 써져 있으므로

 

b->a 형태로 그래프를 만들어 줘야 된다.

 

이 점만 주의하면 쉽게 해결할 수 있는 문제이다.

 

[소스 코드]

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
#include<cstring>
#include <string>
using namespace std;

typedef pair<int, int> Node;

int N, D, C;

vector<vector<Node>> Arr;
vector<int> pathLoad;
vector<bool> visited;
int ResultCount = 0;
int ResultTime = 0;

void Input() {
	cin >> N >> D >> C;
	vector<vector<Node>> Arr2;
	vector<int> pathLoad2;
	vector<bool> visited2;

	Arr2.resize(N + 1);
	pathLoad2.resize(N + 1, INT_MAX);
	visited2.resize(N + 1, false);
	for (int i = 0; i < D; i++) {
		int a, b, time;
		cin >> a >> b >> time;
		Arr2[b].push_back({ time,a });
	}
	Arr = Arr2;
	pathLoad = pathLoad2;
	visited = visited2;


}

void Dijkstra() {
	priority_queue<Node, vector<Node>, greater<Node>> pq;
	pq.push({ 0,C });
	pathLoad[C] = 0;
	while (!pq.empty()) {
		int nowIdx = pq.top().second;
		int ac_Cost = pq.top().first;
		pq.pop();
		if (visited[nowIdx])continue;
		visited[nowIdx] = true;

		for (Node nextNode : Arr[nowIdx]) {
			int nextIdx = nextNode.second;
			int nextCost = nextNode.first;

			if (pathLoad[nextIdx] > pathLoad[nowIdx] + nextCost) {
				pathLoad[nextIdx] = pathLoad[nowIdx] + nextCost;
				pq.push({ pathLoad[nextIdx],nextIdx });
			}
		}
	}
}

void findCountTime() {
	int count = 0;
	int maxTime = -1;
	for (int i = 1; i <= N; i++) {
		if (pathLoad[i] == INT_MAX) {
			count++;
			continue;
		}
		if (maxTime < pathLoad[i]) {
			maxTime = pathLoad[i];
		}
	}
	ResultCount = N - count;
	ResultTime = maxTime;
	
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		Input();
		Dijkstra();
		findCountTime();
		cout << ResultCount << " " << ResultTime << '\n';
	}
}