10282번: Failing Components

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

$O(td\lg n)$

c로부터 도달 가능한 컴퓨터만 감염되며 최단 시간의 최댓값이 마지막 컴퓨터가 감염되는데 걸리는 시간이다.
아래는 다익스트라 알고리즘을 사용했다.

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int t, n, d, c;
int main() {
    scanf("%d", &t);
    while (t--) {
        vector<pair<int, int> > adj[10001];
        scanf("%d%d%d", &n, &d, &c);
        for (int i = 0, x, y, z; i < d; i++) {
            scanf("%d%d%d", &x, &y, &z);
            adj[y].push_back({ x,z });
        }
        int mini[10001], cnt = 0, t = 0;
        priority_queue<pair<int, int> > pq;
        fill(mini + 1, mini + 1 + n, 1e9);
        mini[c] = 0;
        pq.push({ 0,c });
        while (!pq.empty()) {
            int tpos = pq.top().second, tdis = -pq.top().first;
            pq.pop();
            if (mini[tpos] ^ tdis) continue;
            for (auto it : adj[tpos]) {
                if (mini[it.first] > tdis + it.second) {
                    mini[it.first] = tdis + it.second;
                    pq.push({ -mini[it.first],it.first });
                }
            }
        }
        for (int i = 1; i <= n; i++) if (mini[i] < 1e9) t = max(t, mini[i]), cnt++;
        printf("%d %d\n", cnt, t);
    }
    return 0;
}