[BOJ] 10282 : Failing Components

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

---

다익스트라 최단거리 그래프

[ 문제해석 ]

 

 component 들이 서로 의존하는 상황이고, 하나의 component 에서 fail 이 시작하면 다른 의존하는 component 들도 영향을 받는다. 이때, 하나의 component 에서 fail이 시작되면 몇 개의 component 가 fail이 되고, 모든 component 들이 fail 될 때까지 얼마나 시간이 걸리는지 계산하라.

 

[ 알고리즘풀이 ]

 

 fail이  처음 일어나는 component 에서 Dijkstra 알고리즘으로 다른 모든 영향을 줄 수 있는 component 까지의 최단 거리를 구하면 몇 개의 component 가 fail이 되는지 알 수 있다. 또, 모든 component 들이 fail이 될 때까지 걸리는 시간은 최단거리 중 가장 긴 거리이므로 Dijkstra 알고리즘으로 문제를 해결할 수 있다.

 

[ 코드 C++ ]

/*
    시작점 C에서 시작해서 다른 system으로 이동하며 감염을 시키는 문제
    --> c에서 시작해서 다른 system까지 최단거리를 dijkstra를 이용해 구하자.
    --> 경로가 있다면 cnt, 경로 중 가장 긴 거리가 최대 시간!
*/
 
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int t;
    const int INF = 99999999;
    cin >> t;
    while (t--) {
        int n, d, c;
        vector<pair<int, int>> map[10001];
 
        cin >> n >> d >> c;
        for (int i = 0, a, b, c; i < d; i++) {
            cin >> a >> b >> c;
            map[b].push_back({ a, c });
        }
 
        vector<int> distance(n + 1, INF);
        distance[c] = 0;
        priority_queue<pair<int, int>> pq;
        pq.push({ 0, c });
        while (!pq.empty()) {
            int cost = -pq.top().first;
            int here = pq.top().second;
            pq.pop();
 
            if (distance[here] < cost) continue;
            for (int i = 0; i < map[here].size(); i++) {
                int next = map[here][i].first;
                int nextD = cost + map[here][i].second;
                if (nextD < distance[next]) {
                    distance[next] = nextD;
                    pq.push({ -nextD, next });
                }
            }
        }
 
        int cnt = 0, maxL = -INF;
        for(int i = 1; i <= n; i++)
            if (distance[i] != INF) {
                cnt++;
                maxL = max(maxL, distance[i]);
            }
 
        cout << cnt << ' ' << maxL << '\n';
    }
}

[ github ]

https://github.com/travelbeeee/BOJ/blob/master/BOJ10282.cpp

travelbeeee/BOJ

---