백준 알고리즘 10282번 : 해킹

링크

https://www.acmicpc.net/problem/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. 입력이 a,b,s순으로 들어오는데 이는 a가 b를 의존하며, 컴퓨터 b가 감염되면 a도 s초 후에 감염된다라는 뜻이다 즉 입력을 a,b,s,로 받고 그래프에 표현을 해줄 때 adj[b].push_back({c,a}); 이렇게 표현해주어야 한다는 것이다.
2. 마지막 컴퓨터가 감염되기까지 걸리는 시간을 출력한다.
이건 다익스트라를 돌고 각 정점당 최단거리가 가장 긴 것을 골라 출력해주면 된다.

풀이 코드(C++)

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define MAX 10001
#define INF 1e9
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
#define sz(a) int((a).size())

int main(){
  fastio;
  int tc; cin >> tc;
  while(tc--){
    int start = 0;
    pii ans;
    vector<pii> adj[MAX];
    int n,d,c; cin >> n >> d >> c; // n : 컴퓨터 개수, d : 의존성 개수, c : 컴퓨터의 번호(시작 정점)
    start = c;
    ans.second = 0,ans.first = -1;
    for(int i = 0; i < d; i++){
      int u,v,w; cin >> u >> v >> w;
      adj[v].pb({w,u});
    }
    vector<int> dist(MAX, INF);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[start] = 0;
    pq.push({0,start});
    while(!pq.empty()){
      int weight = pq.top().first;
      int cur = pq.top().second;
      pq.pop();
      if(dist[cur] < weight) continue;
      for(auto i = 0; i < adj[cur].size(); i++){
        int next = adj[cur][i].second;
        int nWeight = adj[cur][i].first;
        if(dist[next] > nWeight + weight){
          dist[next] = nWeight + weight;
          pq.push({dist[next], next});
        }
      }
    }
    for(int i = 1; i <= n; i++){
      if(dist[i] != INF){
        ans.second++;
        ans.first = max(ans.first, dist[i]);
      }
    }
    cout << ans.second << ' ' << ans.first << "\n";
  }
  return 0;
}