[백준 10282 - C++] 해킹 : 다익스트라(Dijkstra)

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)가 두 번 이상 존재하지 않는다.

 

출력

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

 

예제 입력 1 

2

3 2 2

2 1 5

3 2 5

3 3 1

2 1 2

3 1 8

3 2 4

예제 출력 1 

2 5 3 6

 

풀이

이 문제에서 의존성 입력은 a, b, s의 순서로 들어오는데, 이는 a가 b에 의존한다는 것이다.

즉, b가 감염되면 s초 후에 a가 감염된다. 

따라서 의존성을 나타내는 way라는 2차원 벡터를 만들어 a, b, s에 대한 정보를 저장한다.

그런 뒤 각각의 컴퓨터를 감염시키는데까지의 가장 작은 경로를 찾기 위해 다익스트라 알고리즘을 적용해야한다.

알고리즘을 적용하여 최단비용 경로를 찾으며 최단 비용은 cost[]배열에 저장한다.

그 수행이 끝나면 감염되지 않는 컴퓨터에 해당하는 경우엔 cost[]값이 -1인 상태일 것이며, 감염되는 경우엔 0이상의 값을 갖고있을 것이다.

따라서 -1이 아닌 것들이 수를 수하고 그것들 중 가장 큰 cost값을 찾아 출력해주면 된다.

 

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;


priority_queue<pair<int, int>> pq;  //비용, 컴퓨터

int cost[10001];

int main(void){
    int test;
    int n, d, c;
    int a, b, s;
    
    int here, here_c;
    int there, there_c;
    int cnt, time;
    
    scanf("%d", &test);
    for(int k=0; k<test; k++){
        
        vector<vector<pair<int, int>>> way; //컴퓨터a, 비용
        cnt = 0;
        time = 0;
        scanf("%d %d %d", &n, &d, &c);
        way.resize(n+1);
        
        for(int i=0; i<d; i++){
            scanf("%d %d %d", &a, &b, &s);
            way[b].push_back(make_pair(a, s));
        }
        for(int i=1; i<=n; i++){
            cost[i] = -1;
        }
        cost[c] = 0;
        
        
        pq.push(make_pair(0, c));
        
        while(!pq.empty()){
            here_c = -pq.top().first;
            here = pq.top().second;
            pq.pop();
            
            if(here_c> cost[here])
                continue;
            
            for(int i=0; i<way[here].size(); i++){
                there = way[here][i].first;
                there_c = here_c + way[here][i].second;
                
                if(cost[there] == -1){
                    cost[there] = there_c;
                    pq.push(make_pair(-there_c, there));
                }
                else if(cost[there] > there_c){
                    cost[there] = there_c;
                    pq.push(make_pair(-there_c, there));
                }
                    
            }
        }
        for(int i=1; i <= n; i++){
            if(cost[i] != -1){
                cnt++;
                if(time < cost[i])
                    time = cost[i];
            }
            
        }
        printf("%d %d\n", cnt, time);
        
    }
}