백준 10282번 - 해킹 (C++)

문제

해결 방법

우선순위 큐(priority_queue)에 현재 감염된 컴퓨터와 연결된 컴퓨터들을 감염시간과 함께 pair<감염 시간, 컴퓨터 숫자> 형식으로 넣어주었다. 큐에서 이를 반복하였다.

또한, 소요 시간이 초기값이 아니라면, 이미 한번 이 컴퓨터가 해킹당했고, 우선순위 큐에서 이전에 탐색되었다는 의미는 이미 더 짧은 소요 시간으로 도달할 수 있다는 의미이기 때문에 continue해주었다.

아쉬웠던 점

없음

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
 
int Hack_Num=0, Hack_Time=0;
void Hacking(vector<vector<pair<int, int>>> &_Vec, vector<int> &_Time_Vec, int _Num)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Que;
    Que.push({ 0, _Num });
 
    pair<int, int> P;
    while (!Que.empty())
    {
        P = Que.top();
        Que.pop();
 
        if (_Time_Vec[P.second] != -1)
            continue;
 
        _Time_Vec[P.second] = P.first;
        Hack_Num++;
        Hack_Time = P.first;
 
        for (auto& i : _Vec[P.second])
            if (_Time_Vec[i.second] == -1)
                Que.push({i.first + _Time_Vec[P.second], i.second});
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int Testcase_Num, Computer_Num, Hacking_Num, Dependency_Num;
    cin >> Testcase_Num;
    
    int a, b, c;
    for (int Test = 0; Test < Testcase_Num; ++Test)
    {
        Hack_Num = 0;
        Hack_Time = 0;
 
        cin >> Computer_Num >> Dependency_Num >> Hacking_Num;
        vector<vector<pair<int, int>>> Vec(Computer_Num+1);
        vector<int> Time_Vec(Computer_Num+1, -1);
 
        for (int i = 0; i < Dependency_Num; ++i)
        {
            cin >> a >> b >> c;
            //b가 감염될때 c초 후, a도 감염
            Vec[b].emplace_back(c, a);
        }
 
        Hacking(Vec, Time_Vec, Hacking_Num);
 
        cout << Hack_Num << " "<< Hack_Time << "\n";
    }
 
    return 0;
}

while문에 보면