Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- UnrealEngine4
- DirectX11
- RVO
- baekjoon
- 백준
- 티스토리챌린지
- Programmers
- 언리얼엔진5
- 팰린드롬 만들기
- C
- directx
- UnrealEngine5
- 2294
- Frustum
- 오블완
- IFileDialog
- DeferredRendering
- RootMotion
- 프로그래머스
- UE5
- 줄 세우기
- softeer
- 1563
- const
- GeeksForGeeks
- winapi
- C++
- NRVO
- Unreal Engine5
- algorithm
Archives
- Today
- Total
Game Develop
[Algorithm]Baekjoon 10282번 : 해킹 본문
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에는 각노드까지의 최단거리가 저장되어있으니, 결국 탐색되어진 것 중 가장 큰값이 모든것들을 포함한 값이 된다.
'Algorithm > Baekjoon' 카테고리의 다른 글
[Algorithm]Baekjoon 1720번 : 타일 코드 (0) | 2024.10.15 |
---|---|
[Algorithm]Baekjoon 21772번 : 가희의 고구마 먹방 (0) | 2024.10.10 |
[Algorithm] Baekjoon 1324번 : 효율적인 해킹 (0) | 2024.10.07 |
[Algorithm] Baekjoon 1477번 : 휴게소 세우기 (1) | 2024.09.24 |
[Algorithm] Baekjoon 14891번 : 톱니바퀴 (1) | 2024.07.16 |