Algorithm/Baekjoon

[Algorithm]Baekjoon 10282번 : 해킹

MaxLevel 2024. 10. 8. 12:32

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

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
 
using namespace std;
 
 
struct Node
{
    int num;
    int time;
};
 
struct cmp
{
    bool operator()(const Node& a, const Node& b)
    {
        return a.time > b.time;
    }
};
 
int t, n, d, c;
int dist[10001] = { 0 };
const int maxNum = 0x3f3f3f3f;
 
void Dijkstra(const vector<vector<Node>>& graph)
{
    priority_queue<Node, vector<Node>, cmp> pq;
    dist[c] = 0;
    pq.push({ c,0 });
    
    while (!pq.empty())
    {
        int curNode = pq.top().num;
        int curTime = pq.top().time;
        pq.pop();
 
        if (curTime > dist[curNode])
        {
            continue;
        }
 
        for (int i = 0; i < graph[curNode].size(); ++i)
        {
            int next = graph[curNode][i].num;
            int nextTime = graph[curNode][i].time;
 
            if (dist[next] > curTime + nextTime)
            {
                dist[next] = curTime + nextTime;
                pq.push({ next, dist[next] }); 
            }
        }
    }
 
    int hackedComputerCounts = 0;
    int hackingTime = 0;
 
    for (int i = 1; i <= n; ++i)
    {
        if (dist[i] != maxNum)
        {
            ++hackedComputerCounts;
            hackingTime = max(hackingTime, dist[i]);
        }
    }
 
    printf("%d %d\n", hackedComputerCounts, hackingTime);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> t;
 
    while (t--)
    {
        cin >> n >> d >> c;
 
        memset(dist, 0x3f, sizeof(dist));
        vector<vector<Node>> graph(n + 1);
        int a, b, s;
 
        for (int i = 0; i < d; ++i)
        {
            cin >> a >> b >> s;
            graph[b].push_back({ a,s });
        }
 
        Dijkstra(graph);
    }
}
 
 
 cs

 

총 감염시간 구하는거에서 살짝 갸우뚱했던 문제. 다익으로 최단거리 전부 구한 후, 또 어떤 로직을 수행해야하나 싶었는데 그냥 탐색한것중에서 가장 값이 큰게 감염시간이다.

어차피 dist에는 각노드까지의 최단거리가 저장되어있으니, 결국 탐색되어진 것 중 가장 큰값이 모든것들을 포함한 값이 된다.