[BOJ G4][C++] 백준 10282번: 해킹

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

10282번: 해킹

 

문제

최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.

최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

• 첫째 줄에 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다(1 ≤ n ≤ 10,000, 1 ≤ d ≤ 100,000, 1 ≤ c ≤ n).
• 이어서 d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다(1 ≤ a, b ≤ n, a ≠ b, 0 ≤ s ≤ 1,000). 이는 컴퓨터 a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다.

각 테스트 케이스에서 같은 의존성 (a, b)가 두 번 이상 존재하지 않는다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 총 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간을 공백으로 구분지어 출력한다.

 

풀이

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> ci;

const int INF = 100000000;

ci dijkstra(int start, int n, vector<vector<ci>>&graph) {
    vector<int> dist(n+1, INF); // dist[i]: i번 컴퓨터가 감염되는데 걸리는 시간
    priority_queue<ci, vector<ci>, greater<>> pq; // {정점, 시작점부터거리}
    
    // 시작 정점 초기화
    dist[start] = 0;
    pq.push({start, 0});
    
    while(!pq.empty()) {
        int node = pq.top().first;
        int weight = pq.top().second;
        pq.pop();
        
        if(weight > dist[node])
            continue;
        
        // 탐색하려는 노드와 연결된 노드들 탐색
        for(int i=0; i<graph[node].size(); i++) {
            int next_node = graph[node][i].first;
            int next_weight = weight + graph[node][i].second;
            
            if(next_weight < dist[next_node]) {
                dist[next_node] = next_weight;
                pq.push({next_node, next_weight});
            }
        }
    }
    
    // 감염된 컴퓨터 수와 시간 구하기
    int hacked=0, time=0;
    for(int i=0; i<n+1; i++) {
        if(dist[i] == INF)
            continue;
        
        hacked++;
        time = max(dist[i], time);
        // 감염될 수 있는 모든 컴퓨터가 감염되는데 걸리는 시간은 INF를 제외한 최댓값
    }
    
    return {hacked, time};
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int t, n,d,c, a,b,s;
    cin >> t;
    
    while(t--){
        cin >> n >> d >> c;
        vector<vector<ci>> graph(n+1); // graph[b]=[{a,s}]: 컴퓨터b가 감염되면 s초 후 a도 감염
        for(int i=0; i<d; i++) {
            cin >> a >> b >> s;
            graph[b].push_back({a,s});
        }
        
        ci ans = dijkstra(c, n, graph);
        
        cout << ans.first << " " << ans.second << "\n";
    }
    
    return 0;
}

/*
 */