글 읽기 - 1005 ACM크래프트 질문드립니다

tikaworld 6년 전 0

조건 섞여있는 경우도 대비해서 두번 돌리게 만들었는데 틀렸다고 나오네요

어느 부분이 문제인지 조언 좀 해주시면 감사하겠습니다!

#include <stdio.h>

int T = 0;
int count = 0;
int result[100001];
int D[100001];
int order[100001][2];
int N = 0, K = 0, W = 0;


int main(void)
{	
	
	scanf("%d", &T);
	while (T > count)
	{
		int DP[100001];
		
		scanf("%d %d", &N, &K);
		for (int i = 1; i <= N; i++)
			scanf("%d", &D[i]);
		for (int i = 1; i <= K; i++)
			scanf("%d %d", &order[i][0], &order[i][1]);
		scanf("%d", &W);
		DP[1] = 0;
		int j = 2;
		while (j >= 0) {
			for (int i = 1; i <= K; i++) {
				int a, b;
				a = order[i][0];
				b = order[i][1];

				if (DP[b] < DP[a] + D[a])
					DP[b] = DP[a] + D[a];
			}
			j--;
		}

		result[count] = DP[W] + D[W];
		count++;
	}
	for (int i = 0; i < T; i++)
		printf("%d\n", result[i]);
	
	return 0;
}

ehddml3 6년 전 0

1. DP값에 대해 초기화 부분이 없습니다.

2. 반례가 있습니다.

1
5 4
1 1 1 1 1
4 5
3 4
2 3
1 2
5

>> 5가 나와야합니다.

3. 위상정렬을 검색해보는게 좋을 것 같습니다.

4. j값을 어느정도 이상으로 키우면 맞을 수도 있습니다. 적당한 크기가 어느 정도인지 생각해보시면 좋을 것 같습니다.

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

문제

문제

출처

ICPC

1005 ACM크래프트 질문드립니다

tikaworld 6년 전 0

ehddml3 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말