Algorithm/BOJ
ACM Craft - 1005
jhg0406
2020. 3. 22. 03:07
|
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
|
//1005 - ACM Craft
#include <iostream>
#include <vector>
using namespace std;
int N, K;
vector<vector<int>> adj;
int cost[1001];
int S;
int cache[1001];
void init()
{
cin >> N >> K;
for(int i = 1; i<=N; ++i)
cache[i] = -1;
adj = vector<vector<int>>(N+1);
for(int i = 1; i<=N; ++i)
cin >> cost[i];
int x, y;
for(int i = 0; i<K; ++i)
{
cin >> x >> y;
adj[y].push_back(x);
}
cin >> S;
}
int dp(int idx)
{
int& ret = cache[idx];
if(ret != -1) return ret;
ret = 0;
for(int i = 0; i<adj[idx].size(); ++i)
{
int there = adj[idx][i];
ret = max(ret, dp(there));
}
ret += cost[idx];
return ret;
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int C; cin >> C;
for(int tn = 0; tn<C; ++tn)
{
init();
cout << dp(S) << "\n";
}
}
|
cs |
https://www.acmicpc.net/problem/1005
1005번: ACM Craft
첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다) 둘째 줄에는 각 건물당 건설에 걸리는 시간 D가 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다) 마지막 줄에는 백준이가 승리하기 위해 건
www.acmicpc.net
ACM Craft
간선의 방향을 역으로 연결하고 dp를 이용해 해결했습니다
C[idx] : idx건물을 완성하는데 걸리는 최소시간
C[idx]는 연결되어있는 다른건물들의 완성시간중 가장 오래걸리는 시간에 idx건물을 짓는 시간을 더해주면 됩니다!
