글 읽기 - 1005번 ACM craft 질문입니다. (틀렸습니다)

10jobss 6년 전 0

위상정렬을 이용해서 풀었는데 50%에서 틀렸습니다가 나왔습니다.

1516번 게임개발과 동일한 문제라고 생각하는데 acm craft는 해결되지 않네요

t배열은 해당 건물 건설 시간 Ft 배열은 누적시간 입니다.

잘못된 부분 알려주시면 감사하겠습니다.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
	int tc;
	scanf("%d", &tc);
	while (tc--) {
		int n, k, w;
		scanf("%d%d", &n, &k);
		vector<vector<int> > adj(n + 1);
		queue<int> q;
		int in[501] = { 0 }, t[501] = { 0 }, Ft[501] = { 0 };
		for (int i = 1; i <= n; ++i) scanf("%d", &t[i]);
		while (k--) {
			int x, y;
			scanf("%d%d", &x, &y);
			adj[x].push_back(y);
			in[y]++;
		}
		scanf("%d", &w);
		for (int i = 1; i <= n; ++i) {
			if (in[i] == 0) {
				q.push(i);
				Ft[i] = t[i];
			}
		}
		while (q.size()) {
			int prev = q.front();
			q.pop();
			for (int i = 0; i < adj[prev].size(); ++i) {
				int next = adj[prev][i];
				if (--in[next] == 0) q.push(next);
				Ft[next] = max(Ft[next], Ft[prev] + t[next]);
			}
		}
		printf("%d\n", Ft[w]);
	}
	return 0;
}

10jobss 6년 전 0

배열의 크기를 잘못 잡았었습니다. 해결했습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1005번 ACM craft 질문입니다. (틀렸습니다)

10jobss 6년 전 0

10jobss 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말