백준 10282번 : 해킹

문제링크 :https://www.acmicpc.net/problem/10282

10282번: 해킹

 문제설명 

 

1. 컴퓨터 끼리 서로 의존 하는데 그냥 단방향 그래프라고 봐도무방

2. a컴퓨터가 b컴퓨터에 의존하고있다면 b가 바이러스에 감염되면 a도감염 -> 걸리는 시간 이 따로 주어진다.

3. 처음 감염된 컴퓨터가 주어질때 ,총 몇개의 컴퓨터가 감염되고 가장 마지막에 감염되는 컴퓨터가 감염되는데 걸리는

  시간 출력

 

 알고리즘 

 

1. 다익스트라 알고리즘을 이용하여 처음 감염된 컴퓨터에서 다른 컴퓨터로 감염될 수있는 경우를 모두 업데이트

2. 감염된 컴퓨터 (check[i]!=INF)  의 갯수와 컴퓨터가 감염되는데 걸리는 시간의 최댓값을 출력.

 

 코드 

 

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int, int> P;
 
//컴퓨터 갯수 ,의존성 갯수 , 해킹당한 번호 
int n, d, c;
int check[10001];
vector<P> v[10001];
int visited[10001];
void dijkstra(int start) {
    //자기자신
    check[start] = 0;
 
    priority_queue<P> PQ;
    PQ.push(P(0, start));
 
    while (!PQ.empty()) {
        int curr = PQ.top().second;
        int dist = -PQ.top().first;
        PQ.pop();
 
        if (check[curr] < dist)continue;
 
        
        for (int i = 0; i < v[curr].size(); i++) {
            int next = v[curr][i].first;
            int next_dist = dist + v[curr][i].second;
 
            if (next_dist < check[next]) {
                check[next] = next_dist;
                PQ.push(P(-next_dist, next));
            }
        }
    }
}
 
 
 
 
 
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(0);
 
    int T;
    cin >> T;
    for (int j = 0; j < T; j++) {
 
        cin >> n >> d >> c;
 
        for (int i = 0; i < d; i++) {
            int a1, a2, a3;
            cin >> a1 >> a2 >> a3;
 
            //단방향 그래프
            v[a2].push_back(P(a1, a3));
        }
 
        //배열 초기화 
        for (int i = 0; i <= n; i++) {
            check[i] = 1000000000;
            visited[i] = 0;
        }
 
        //다익스트라 
        dijkstra(c);
 
        //감염 컴퓨터 갯수
        int cnt = 0;
 
        //감염 시간
        int Time = 0;
 
        for (int i = 1; i <= n; i++) {
            if (check[i] != 1000000000) {
                cnt++;
                Time = max(Time, check[i]);
            }
        }
 
        cout << cnt << " " << Time << "\n";
        
        //벡터 초기화
        for (int i = 0; i <= n; i++) {
 
            int Size = v[i].size();
            for (int k = 0; k < Size; k++) {
                v[i].pop_back();
            }
            
        }
            
    }
}