-
728x90반응형
출처:https://www.acmicpc.net/problem/10282
10282번: 해킹
문제 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다. 최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는
www.acmicpc.net
문제
최흉최악의 해커 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)가 두 번 이상 존재하지 않는다.
출력
각 테스트 케이스마다 한 줄에 걸쳐 총 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간을 공백으로 구분지어 출력한다.
풀이
감염 컴퓨터의 출발점이 주어지고 결국엔 방문한 노드들 중에서 가장 최단 시간의 경로를 통해 감염을 시키고 최종적으로 감염이 된 컴퓨터들 중에 가장 감염시간이 오래걸린 컴퓨터를 출력하면 된다. 이것은 다익스트라를 써서 방문시 최단경로로 노드를 접근 하는 경로로 계속해서 dist배열을 갱신시키고 난 후 감염이 다 끝나면 최종적으로 가장 시간이 오래걸린 노드의 dist값만 구해주면 된다는 뜻이다.
코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters// #10282 해킹 #include <iostream> #include <cstring> #include <vector> #include <algorithm> #include <queue> #define INF 1000000000 #define endl '\n' using namespace std; typedef struct info{ int to, dis; }; typedef pair<int, int> p; int dist[10001]; vector <info> v[10001]; int test; int n, d, st;//노드 수, 간선 수, 감염 시작 노드 void dijkstra() { priority_queue<p, vector<p>, greater<p>>pq; pq.push({ 0,st}); dist[st] = 0; while (!pq.empty()) { int fnum = pq.top().second; int fdis = pq.top().first; pq.pop(); if (dist[fnum] != fdis)continue; for (auto it : v[fnum]) { int nnum = it.to; int ndis = it.dis + fdis; if (dist[nnum] > ndis) { dist[nnum] = ndis; pq.push({ ndis,nnum }); } } } } void Init() { for (int i = 1; i <= n; i++) { v[i].clear(); } } void Input() { cin.tie(0); cin.sync_with_stdio(0); cin >> n >> d >> st; int a, b, dis; for (int i = 0; i < d; i++) { cin >> a >> b >> dis; v[b].push_back({ a,dis }); } fill(dist, dist + n + 1, INF); } int main() { cin >> test; while (test--) { Input(); dijkstra(); int cnt=0;//감염 노드 갯수 int ans = 0;//감염 시간 for (int i = 1; i <= n; i++) { if (dist[i] != INF) { ans = max(ans, dist[i]); cnt++; } } cout << cnt << " " << ans << endl; Init(); } } 728x90반응형'Code > BOJ' 카테고리의 다른 글
#17136 색종이 붙이기 (0) 2020.03.12 #2610 회의준비 (0) 2020.03.07 #12094. 2048 (Hard) (0) 2020.03.06 #16235 나무 재테크 (0) 2020.03.06 #17143 낚시왕 (0) 2020.03.06