BAEKJOON
BAEKJOON 1005번: ACM Craft
초음속바지벗기
2022. 3. 1. 22:13
728x90
https://www.acmicpc.net/problem/1005
1005번: ACM Craft
첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부
www.acmicpc.net
풀이
D[i]={i번째 건물을 짓는데 걸리는 총 시간}
D를 위와 같이 정의 하면, 마지막으로 짓고 싶은 건물 W에서 시작하여 각 건물에 대해 건물을 짓기 위해 필요한 건물들을 짓는데에 필요한 총 시간 중 최댓값만 가져오면 됩니다.
코드
|
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
|
#include <bits/stdc++.h>
using namespace std;
vector<int>vi[1003];
int D[1003],dp[1003];
int f(int i){
int &ret=dp[i];
if(ret!=-1)return ret;
dp[i]=0;
for(int j=0;j<(int)vi[i].size();j++){
ret=max(ret,f(vi[i][j]));
}
ret+=D[i];
return ret;
}
int main(){
int T;scanf("%d",&T);
while(T--){
memset(dp,-1,sizeof(dp));
int N,K,X,Y,W;
scanf("%d%d",&N,&K);
for(int i=1;i<=N;i++)vi[i].clear();
for(int i=1;i<=N;i++)scanf("%d",&D[i]);
for(int i=1;i<=K;i++){
scanf("%d%d",&X,&Y);
vi[Y].push_back(X);
}
scanf("%d",&W);
printf("%d\n",f(W));
}
return 0;
}
|
cs |
728x90