백준 10282번 해킹 C++

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

 

다익스트라를 이용해서 풀었다.

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

#include <bitset>

using namespace std;
using int64 = long long;

struct VertexCost;
vector<vector<VertexCost>> vertexs;

struct VertexCost {
	bool operator<(const VertexCost& other) const {
		return cost < other.cost;
	}
	bool operator>(const VertexCost& other) const {
		return cost > other.cost;
	}
	int vertex;
	int cost;
};

void Dijikstra(int start, int n) {
	vector<int> best(n + 1, INT_MAX);
	priority_queue<VertexCost, vector<VertexCost>, greater<VertexCost>> pq;
	pq.push({ start,0 });
	best[start] = 0;

	while (!pq.empty()) {
		auto curr = pq.top();
		pq.pop();

		if (curr.cost > best[curr.vertex])
			continue;

		for (auto a : vertexs[curr.vertex]) {
			int nextCost = curr.cost + a.cost;
			if (nextCost >= best[a.vertex])
				continue;
			best[a.vertex] = nextCost;
			pq.push({ a.vertex,nextCost });
		}
	}
	int cnt = 0;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (best[i] == INT_MAX) continue;
		cnt++;
		ans = max(ans, best[i]);
	}
	cout << cnt << " " << ans << "\n";
}

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

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