글 읽기 - ACM Craft C++ 시간초과를 해결하고 싶습니다

mk970205 5년 전 0

Stack을 통한 DFS로 풀려고 했고, 다른 사람의 조언을 받아 cin cout 속도도 빠르게 했는데, 자꾸 시간초과가 뜹니다. 어떻게 해야 좋을까요?

#include<iostream>
#include<vector>
#include<stack>

using namespace std;
typedef pair<int, int> ip;

int main() {

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

	int T, n, k, x;
	cin >> T;

	int* build_time;
	for (int i = 0; i < T; i++) {
		vector<vector<int>> tech_tree;
		cin >> n >> k;
		build_time = new int[n];
		for (int j = 0; j < n; j++) {
			cin >> build_time[j];
			tech_tree.push_back(vector<int>());
		}
		for (int j = 0; j < k; j++) {
			int tmp1, tmp2;
			cin >> tmp1 >> tmp2;
			tech_tree[tmp2 - 1].push_back(tmp1 - 1);
		}
		cin >> x;
		ip node = make_pair(x - 1, build_time[x - 1]);

		stack<ip> dfs = stack<ip>();
		dfs.push(node);
		int max_time = -1;
		while (!dfs.empty()) {
			ip tmp = dfs.top();
			dfs.pop();
			if (tech_tree[tmp.first].empty()) {
				max_time = (max_time < tmp.second) ? tmp.second : max_time;
				continue;
			}
			for (int j = 0; j < tech_tree[tmp.first].size(); j++) {
				int idx = tech_tree[tmp.first][j];
				int cost = tmp.second + build_time[idx];
				dfs.push(make_pair(idx, cost));
			}
		}

		cout << max_time << '\n';

		delete(build_time);
	}
}