[백준] 10282 해킹

서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.

• a ← b : a가 b를 의존한다.

위 조건을 활용하여 테스트케이스를 그림으로 표현해보면 다음과 같은 그래프로 나타낼 수 있다.

TC2를 보았을 때 3은 1을 의존하고, 8초만에 감염된다. 하지만 3은 2도 의존하고, 이 2는 1을 의존하기 때문에 이 경로로 감염되는 시간을 구하면 2+4=6초로 시간상 더 빨리 감염된다. 따라서 3대가 6초 시간을 걸려 감염된다.

 

해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오. → 처음 해킹된 컴퓨터는 하나이다. 즉, 시작점이 하나이다. (처음 그림을 그렸을 때 간선 흐름에만 집중해 벨만포드($VE$)로 접근하려고 했지만 시작점이 하나이므로 다익스트라($E\log{V}$)로 접근해도 된다. 제한시간은 2초, 테케 100개, 노드 $10^4$, 간선 $10^5$이므로 벨만포드도 가능할것)

 

그리고 다익스트라로 구한 각 노드(컴퓨터)가 감염되기까지의 최단시간을 구할 수 있고, 만약 감염되지 않는다면 초기상태와 똑같이 무한대 값을 가진다. 따라서 최단시간 중 무한대 값을 가지지 않는 경우를 카운트하면 감염된 컴퓨터를 구할 수 있고, 이 최단시간 중 가장 큰 시간을 구하면 마지막 컴퓨터가 감염되기까지 걸리는 시간을 구할 수 있다. ($V$)

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define MAX_n 10001
#define INF 987654321

int T, n, d, c, a, b, s, ans_node, ans_time;
vector<pair<int, int>> edges[MAX_n];
int dist[MAX_n];

void init_() {
    fill(&dist[0], &dist[MAX_n], INF);
    for (int i = 0; i < MAX_n; ++i) {
        edges[i].clear();
    }
    ans_node = 0;
    ans_time = 0;
}

void dijk() {
    priority_queue<pair<int, int>> que;
    que.push({0, c});
    dist[c] = 0;

    pair<int, int> cur;
    int cur_node, cur_cost, nxt_node, nxt_cost;
    while (!que.empty()) {
        cur = que.top();
        cur_node = cur.second;
        cur_cost = -cur.first;
        que.pop();

        if (dist[cur_node] < cur_cost) continue;

        for (pair<int, int> nxt : edges[cur_node]) {
            nxt_node = nxt.first;
            nxt_cost = nxt.second;
            if (dist[nxt_node] > nxt_cost + cur_cost) {
                dist[nxt_node] = nxt_cost + cur_cost;
                que.push({-dist[nxt_node], nxt_node});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> T;
    while (T--) {
        cin >> n >> d >> c;
        init_();
        for (int i = 0; i < d; ++i) {
            cin >> a >> b >> s;
            edges[b].push_back({a, s});
        }

        dijk();

        for (int i = 1; i <= n; ++i) {
            if (dist[i] < INF) {
                ++ans_node;
                ans_time = max(ans_time, dist[i]);
            }
        }

        cout << ans_node << " " << ans_time << '\n';
    } 

    return 0;
}