[백준 알고리즘] 1005번 ACM Craft c++

 

2차원 벡터 d의 i번째 원소에 i번 건물보다 선행되어야할 건물의 정보를 저장했다.

time벡터에는 선행작업이 없는 건물을 찾아 delay[i]를, 나머지 time에는 -1를 저장했다.

그 이후 time[w]의 결과를 찾을 때까지 1~n까지를 반복하며

선행될 건물의 time값이 모두 구해진 경우에 해당 위치의 time값을 구했다.

(다이나믹 프로그래밍)

 

+처음 제출 시 시간이 높게 나와서 c++에서 알고리즘 문제 풀이 시 cin,cout사용시 속도를 줄일 수 있는

ios_base::sync_with_stdio(false); cin.tie(null); cout.tie(null);

를 알게 되었다. 대신 getchar등 c에서 사용하는 입출력함수를 같이 사용하면 안 된다.

+cout << endl 을 사용하는 것보다 cou<<"\n"를 사용하는 것이 속도면에서 좋다.

#include <iostream>
#include <vector>



using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t, n, k, w;
	int delay[1001];

	cin >> t;
	while(t--){
		cin >> n >> k;

		for(int i=1; i<=n; i++){
			cin >> delay[i];
		}

		int x,y;

		vector<vector<int>> d(n+1);
		vector<int> time(n+1,0);
	
		for(int i=0; i<k; i++){
			cin >> x >> y;
			d[y].push_back(x);
			time[y] ++;
		}

		cin >> w;

		for(int i=1; i<=n; i++){
			if(time[i] == 0){
				time[i] = delay[i];
			}
			else{
				time[i] = -1;
			}
		}
		while(time[w] == -1){
			for(int i=1; i<=n; i++){
				if(time[i] == -1){
					int j, max_time = -1;
					for(j=0; j < d[i].size(); j++){
						if(time[d[i][j]] == -1)
							break;
						else{
							max_time = max(time[d[i][j]], max_time);
						}
					}
					if(j==d[i].size()){
						time[i] = delay[i] + max_time;
						if(i==w)
							break;
					}
				}
			}
		}
		cout << time[w]<<"\n";
	}
	return 0;
}