백준 10282: 해킹

#include <iostream>
#include <vector>
#include <utility> // pair
#include <cstring>
#include <queue>
#include <algorithm>
#define MAX 10001
#define INF 0x7FFFFFFF
using namespace std;

vector< pair<int, int> > graph[MAX]; // graph[from] = ((to, weight), (to, weight), ...)
vector<int> dist(MAX, INF);

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

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

		priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq; // (weight, from)

		pq.push(make_pair(0, c));
		dist[c] = 0;

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

			if (dist[from] < weight) continue;
			
			int edge = graph[from].size();
			for (i = 0; i < edge; i++) {
				int to = graph[from][i].first;
				int newDist = weight + graph[from][i].second;

				// 더 짧은 경로를 발견하면 dist를 update하고 pq에 집어넣음
				if (newDist < dist[to]) {
					dist[to] = newDist;
					pq.push(make_pair(newDist, to));
				}
			}
		}

		int cnt, ans;
		cnt = ans = 0;
		for (i = 1; i <= n; i++) {
			if (dist[i] != INF) {
				ans = max(ans, dist[i]);
				cnt++;
			}
		}
		cout << cnt << " " << ans << endl;
	}
	return 0;
}