[백준/Baekjoon] 10282 해킹C++ :: Dijkstra

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

10282번: 해킹

---

1. Logic

단순 다익스트라에 간단한 후처리를 요구하는 문제이다.

다익스트라로 첫 해킹을 당한 컴퓨터부터 시작해서 감염을 시키고 다익스트라 이후 dist배열 전체를 순회하여 INF가 아닌 배열들의 갯수를 세주면 감염되는 컴퓨터 수를 구할 수 있고 걸리는 시간은 전체 배열을 순회하며 가장 큰 배열의 값을 구하면 된다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;
int dist[10001];
vector<pair<int, int>> input[10001];

int n, d, c;

void dijkstra() {
    memset(dist, INF, sizeof(dist));

    priority_queue<pair<int, int>> pq;

    dist[c] = 0;

    pq.push({0, c});

    while(!pq.empty()) {
        int cur = pq.top().second;
        int cost = -pq.top().first;

        pq.pop();

        if(dist[cur] < cost) continue;

        for(int i = 0; i < input[cur].size(); i++) {
            int next = input[cur][i].second;
            int ncost = input[cur][i].first + cost;

            if(dist[next] > ncost) {
                dist[next] = ncost;
                pq.push({-ncost, next});
            }
        }
    }

    int infectCnt = 0;
    int ans = 0;

    for(int i = 1; i <= n; i++) {
        if(dist[i] != INF) {
            infectCnt++;
            ans = max(ans, dist[i]);
        }
    }
    cout << infectCnt << " " << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int t;
    cin >> t;

    while(t--) {
        for(int i = 0; i < 10001; i++) {
            input[i].clear();
        }
        cin >> n >> d >> c;

        for(int i = 0; i < d; i++) {
            int a, b, s;
            cin >> a >> b >> s;

            input[b].push_back({s, a});
        }

        
        dijkstra();
    }
}

 

 

---

3. Feedback

다익스트라 조금 더 체화 필요함

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90