BOJ 10282 : 해킹

www.acmicpc.net/problem/10282

10282번: 해킹

 

우리는 여기서 모든 가능한 컴퓨터가 해킹되려면 컴퓨터가 해킹되는 경로 중에서 가장 시간이 최소인 경로를 찾아야 된다.

 

이는 다익스트라로 구할 수 있다.

 

#include <bits/stdc++.h>
#define sanic ios_base::sync_with_stdio(0)
#define MOD 1000000
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const ll MEM = 10006;
const ll INF = 1e9+7;
ll n,m,d,t;
ll cost[MEM];
int main() {
    sanic; cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        vector<p> g[MEM];
        cin >> n >> m >> d;
        for(int i=0; i<m; i++){
            ll s,e,c;
            cin >> s >> e >> c;
            g[e].push_back({s,c});
        }
        priority_queue<p, vector<p>, greater<p>> q;
        fill(cost+1, cost+n+1, INF);
        cost[d] = 0;
        q.push({d,0});
        while(!q.empty()){
            ll c=q.top().first;
            ll cl=q.top().second;
            q.pop();
            if(cost[c]<cl) continue;
            for(auto &u: g[c]){
                int nx=u.first, cc = u.second;
                if(cost[nx]>cost[c]+cc){
                    cost[nx] = cost[c]+cc;
                    q.push({nx, cost[nx]});
                }
            }
        }
        ll k=-INF;
        ll cnt=0;
        for(int i=1; i<=n; i++){
            if(cost[i]!=INF){
                cnt++;
                k = max(k, cost[i]);
            }
        }
        cout << cnt << ' ' << k << '\n';
    }
}