[백준 10282] 해킹

문제 풀이

 

a b s 가 주어지면, b가 감염되면 s초 후에 컴퓨터 a가 감염된다.

이 말은 즉슨 b부터 감염을 시작하면 a까지의 도달하는 비용은 s초다.

 

출발 노드로부터 다익스트라 알고리즘을 순회하면 문제를 해결할 수 있다.

감염된 컴퓨터의 수는 dist 배열에서 INF가 아닌 컴퓨터를 카운팅 하면 된다.

모든 컴퓨터가 감염되기까지 걸린 시간 역시 INF가 아닌 dist 배열에서 가장 큰 수를 저장해서 출력하면 된다.

 

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int t, n, d, c;

const int INF = 987654321;
typedef pair<int, int> pii;

vector<pii> adj[10001];
int dist[10001];


void dijkstra(int start)
{
    fill(dist, dist + 10001, INF);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});
    dist[start] = 0;
    while(!pq.empty())
    {
        int distance = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        
        if(dist[cur] < distance) continue;
        
        for(int i = 0; i < adj[cur].size(); i++)
        {
            int next = adj[cur][i].first;
            int nextDistance = adj[cur][i].second + distance;
            if(dist[next] > nextDistance)
            {
                dist[next] = nextDistance;
                pq.push({nextDistance, next});
            }
        }
    }
    
    int time = 0;
    int cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        if(dist[i] != INF)
        {
            cnt++;
            time = max(time, dist[i]);
        }
    }
    
    cout << cnt << ' ' << time << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> t;
    while(t--)
    {
        cin >> n >> d >> c;
        
        for(int i = 0; i < 10001; i++)
            adj[i].clear();
        
        for(int i = 0; i < d; i++)
        {
            int a, b, s;
            cin >> a >> b >> s;
            adj[b].emplace_back(a,s);
        }
        
        dijkstra(c);
    }
    
    return 0;
}