글 읽기 - 1005번 문제 데이터 잘못된 것 같습니다

annaria 6년 전 2

0 ≤ D ≤ 1000

이 조건이랑 데이터랑 안맞는것 같습니다.

D값이 1000넘으면 시간초과가 나오도록

if (dat[i] > 1000) while (1);

이렇게 넣으니 시간초과나네요.

const int MX = 100000011;
int n, dat[1001], d[1001], tr;
vector<int> v1[1001];

int dp(int id)
{
	if (d[id] != -1) return d[id];
	if (id == tr) return dat[id];
	d[id] = -1 * MX;
	if (v1[id].empty()) return d[id];

	for (int x : v1[id])
	{
		d[id] = max(d[id], dat[id] + dp(x));
	}

	return d[id];
}

int main()
{
	int test_case, test; scanf("%d", &test_case);
	for (test = 1; test <= test_case; test++)
	{
		int k; scanf("%d %d", &n, &k);
		memset(d, -1, sizeof(d));
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &dat[i]);
            if (dat[i] > 1000) while (1); // D가 1000을 넘으면 시간초과
			v1[i].clear();
		}
		int a, b, cnt[1001] = {};
		for (int i = 1; i <= k; i++)
		{
			scanf("%d %d", &a, &b);
			v1[a].push_back(b);
			cnt[b]++;
		}
		scanf("%d", &tr);
		int ans = -1 * MX;
		for (int i = 1; i <= n; i++)
		{
			if (!cnt[i])
			{
				ans = max(ans, dp(i)); 
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

startlink 6년 전 0

조건을 수정했습니다.

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

문제

문제

출처

ICPC

1005번 문제 데이터 잘못된 것 같습니다

annaria 6년 전 2

startlink 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말