[백준 / BOJ] C++ 10282 해킹

10282번: 해킹

 

문제

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

10282번: 해킹

 

 

풀이

의존성이 있는 컴퓨터에 바이러스가 전염되는 시간과 몇 대의 컴퓨터가 감염되었는지 구하는 문제다. 다익스트라 알고리즘으로 풀 수 있다. 다익스트라 알고리즘에 대해 잘 모른다면 아래 링크를 통해 알아보자.

[다익스트라 알고리즘 알아보기]

 

!! 신경 쓸 점이 두 가지 있다.

1. 테스트 케이스가 여러 개이므로 배열과 변수 초기화에 신경 써야 한다.

2. a가 b에 의존하고 있으므로 b가 감염되면 a가 영향을 받는다. 따라서 간선의 방향에 주의해야 한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

#define INF 2147483647

int N, D, C;
vector<pair<int, int>> graph[10001];
vector<int> dist(10001, INF), visited(10001, 0);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

void init() {
  for (int i = 1; i <= N; i++) {
    visited[i] = 0;
    dist[i] = INF;
  }
}

void dijkstra(int s) {
  init();
  dist[s] = 0;
  pq.push({0, s});
  while (!pq.empty()) {
    int curr;
    do {
      curr = pq.top().second;
      pq.pop();
    } while (!pq.empty() && visited[curr]);
    if (visited[curr])
      break;
    visited[curr] = 1;
    for (auto &p : graph[curr]) {
      int next = p.first, d = p.second;
      if (dist[next] > dist[curr] + d) {
        dist[next] = dist[curr] + d;
        pq.push({dist[next], next});
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    cin >> N >> D >> C;
    for (int i = 1; i <= N; i++)
      graph[i].clear();
    for (int i = 0; i < D; i++) {
      int a, b, s;
      cin >> a >> b >> s;
      graph[b].push_back({a, s});
    }
    dijkstra(C);
    int cnt = 0, t = 0;
    for (int i = 1; i <= N; i++)
      if (dist[i] != INF) {
        cnt++;
        t = max(t, dist[i]);
      }
    cout << cnt << ' ' << t << '\n';
  }
  return 0;
}