백준 10282 : 해킹

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

어떤 컴퓨터x 가 동시에  a,b,c 3대의 컴퓨터를 의존한다고 했을 때 그 컴퓨터x 는 a 또는 b, c 에 의해 감염될 수 있다.

근데 이때 a,b,c 중 가장 감염이 빠른 컴퓨터 기준 걸린 시간 + s 만큼 컴퓨터x 가 감염이 되므로 결국 최단경로를 찾는

다익스트라 알고리즘이다.

최소 경로를 갱신할 때 만약 이전 dist값이 INF이면 처음 감염된 컴퓨터이므로 count값을 ++ 시켜주는 것으로 감염된

컴퓨터의 총 개수를 구할 수 있고 INF가 아닌 컴퓨터들의 dist중 max값이 가장 마지막 컴퓨터가 감염완료된 시점으로

볼 수 있다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

#include <iostream> #include <vector> #include <queue> #define INF 1000000000 #define MAX 10001 using namespace std; struct Com{ int dist = INF; vector<pair<int, int>> next; bool operator < (const Com &c) const { return dist > c.dist; } }; Com com[MAX]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int tc; cin >> tc; while(tc--){ int n, d, c; cin >> n >> d >> c; for(int i = 1; i <= n; i++){ com[i].dist = INF; com[i].next.clear(); } while(d--){ int a, b, w; cin >> a >> b >> w; com[b].next.push_back(make_pair(w, a)); } int count = 1; int maxTime = 0; priority_queue<Com> pq; com[c].dist = 0; pq.push(com[c]); while(!pq.empty()){ Com curCom = pq.top(); pq.pop(); for(pair<int, int> pa : curCom.next){ int w = pa.first; int nIdx = pa.second; if(com[nIdx].dist > curCom.dist + w){ if(com[nIdx].dist == INF) count++; com[nIdx].dist = curCom.dist + w; pq.push(com[nIdx]); } } } for(int i = 1; i <= n; i++){ int td = com[i].dist; if(td > maxTime && td != INF) maxTime = td; } cout << count << " " << maxTime << '\n'; } return 0; }