문제 풀이
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;
}
'Algorithm' 카테고리의 다른 글
[백준 14221] 편의점 (0) | 2021.11.04 |
---|---|
[백준 18352] 특정 거리의 도시 찾기 (0) | 2021.11.04 |
[백준 1251] 단어 나누기 (0) | 2021.10.24 |
[백준 5670] 휴대폰 자판 (0) | 2021.10.19 |
[백준 4358] 생태학 (0) | 2021.10.19 |