https://www.acmicpc.net/problem/10282
최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.
최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다. 각 테스트 케이스는 다음과 같이 이루어져 있다.
각 테스트 케이스마다 한 줄에 걸쳐 총 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간을 공백으로 구분지어 출력한다.
..엄청나게 많이 틀린 문제다..;;
일반적인 다익스트라지만 문제가 원하는 것을 정확하게 파악하는 것이 중요하다.
문제의 요구 조건을 정확히 따져보면
1. 입력이 a,b,s순으로 들어오는데 이는 a가 b를 의존하며, 컴퓨터 b가 감염되면 a도 s초 후에 감염된다라는 뜻이다 즉 입력을 a,b,s,로 받고 그래프에 표현을 해줄 때 adj[b].push_back({c,a});
이렇게 표현해주어야 한다는 것이다.
2. 마지막 컴퓨터가 감염되기까지 걸리는 시간을 출력한다.
이건 다익스트라를 돌고 각 정점당 최단거리가 가장 긴 것을 골라 출력해주면 된다.
#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;
}