BOJ 10282 해킹

해킹 [골드 4]

---

문제 링크

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

풀이

감염된 시작 노드로부터 퍼트릴 수 있는 컴퓨터의 갯수와 가장 먼 컴퓨터를 구해 출력한다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

#define MAX 10001

using namespace std;

int t,n,d,c;
int a,b,s;
int cost[MAX];

void dijkstra(vector<pair<int,int>> edge[]) {
    
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, c});

    cost[c] = 0;

    while(!pq.empty()) {

        auto elem = pq.top();
        pq.pop();

        int current_vertex = elem.second;
        int current_cost = elem.first;

        if(cost[current_vertex] < current_cost)
            continue;

        for(int i=0; i<edge[current_vertex].size(); i++) {
            int next_vertex = edge[current_vertex][i].first;
            int next_cost = edge[current_vertex][i].second;

            if(next_cost + current_cost < cost[next_vertex]) {
                cost[next_vertex] = next_cost + current_cost;
                pq.push({next_cost + current_cost, next_vertex});
            }
        }
    }

    int cnt=0, res=0;
    for(int i=1; i<=n; i++) {
        if(cost[i] != 1e9) {
            cnt++;
            if(res < cost[i]) {
                res = cost[i];
            }
        }
    }

    cout << cnt << " " << res << "\n";
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> t;
    while (t--) {
        vector<pair<int, int>> edge[MAX];
        cin >> n >> d >> c;

        fill_n(cost, MAX, 1e9);
        
        for (int i = 0; i < d; i++) {
            cin >> a >> b >> s;
            edge[b].push_back({ a,s });            // b 감염 시 a는 s초 후 감염
        }

        dijkstra(edge);

    }

    return 0;
}