[BOJ] 10282 : 해킹

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

int n, m, s;
struct edg {
    int idx, dst;
    bool operator <(edg A)const {
        return dst > A.dst;
    }
};

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

    int tc;
    for (cin >> tc; tc; tc--) {
        cin >> n >> m >> s;

        vector<vector<edg> > gph(n+1);
        vector<int> dst(n+1, 1e9);
        priority_queue<edg> pq;

        for (int i = 0, u, v, w; i < m; i++) {
            cin >> u >> v >> w;
            gph[v].push_back({ u,w });
        }

        pq.push({ s,dst[s]=0 });
        while (!pq.empty()) {
            edg now = pq.top();
            pq.pop();
            if (now.dst != dst[now.idx]) continue;
            for (edg nxt : gph[now.idx]) {
                if (dst[nxt.idx] > dst[now.idx] + nxt.dst) {
                    dst[nxt.idx] = dst[now.idx] + nxt.dst;
                    pq.push({ nxt.idx,dst[nxt.idx] });
                }
            }
        }

        int cnt = 0, val = 0;
        for (int i = 1; i <= n; i++) if (dst[i] != 1e9) {
            cnt++;
            val = max(val, dst[i]);
        }

        cout << cnt << " " << val << "\n";
    }

    return 0;
}