[알고리즘] 백준 10282번: 해킹 (C++)

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

10282번: 해킹

1) "a가 b에 s만큼의 의존성을 가지고 있다." == "b에서 a로 가는 비용이 s다." >> 다익스트라 사용

 

2) 그래프를 전역 변수로 선언했기 때문에 한 케이스가 끝나면 그래프를 리셋을 해주었다.>>

>> 사실 vector<pair<int, int>> graph[MAX]를 인자로 넘기는 방법을 몰랐음.

>> 인자로 넘기는 방법을 알면 리셋하는 시간이 없어져서 조금 줄일 수 있지 않을까 싶다.

 

3) 거리가 INF인 것은 넘기고, INF가 아닌 것은 cnt를 하며 그와 동시에 최댓값을 구한다.

 

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <cmath>
#define MAX 10000 + 1
#define INF 987654321
using namespace std;

int T;
vector<pair<int, int>> graph[MAX];

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

vector<int> dijkstra(int node, int n) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
	vector<int> dist(n + 1, INF);
	dist[node] = 0;
	pq.push(make_pair(node, 0));
	while (!pq.empty()) {
		int now = pq.top().first;
		int cost = pq.top().second;

		pq.pop();
		
		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].first;
			int nextCost = graph[now][i].second;
			if (cost + nextCost < dist[next]) {
				dist[next] = cost + nextCost;
				pq.push(make_pair(next, dist[next]));
			}
		}
	}
	return dist;
}

void resetGraph(int n) {
	for (int i = 1; i <= n; i++) {
		while (!graph[i].empty()) {
			graph[i].pop_back();
		}
	}
	return;
}

int main() {
	cin >> T;

	for (int t = 0; t < T; t++) {
		int n, d, c;
		cin >> n >> d >> c;
		for (int i = 0; i < d; i++) {
			int a, b, s;
			cin >> a >> b >> s;
			graph[b].push_back(make_pair(a, s));
		}

		vector<int> temp = dijkstra(c, n);

		int cnt = 0;
		int maxValue = 0;
		for (int i = 1; i <= n; i++) {
			if (temp[i] == INF) {
				continue;
			}
			cnt++;
			maxValue = max(maxValue, temp[i]);
		}
		cout << cnt << ' ' << maxValue << '\n';
		resetGraph(n);
	}
	return 0;
}