글 읽기 - 1005번 질문입니다.

znxenter 8년 전 0

지어야하는 건물부터 역순으로 bfs를 하면서

건물을 지어야하는 시간을 result에 갱신하도록 코드를 짰는데

채점 25%에서 막히네요 ㅠㅠ

어디서 문제가 있는걸까요...

#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;

int testcase;
int n, k;
int d[1001];
int result[1001];
int check[1001];
int order[1001][1001];
int start, dest;

int main() {
	int temp1, temp2, current, count;
	queue <int> bfs;

	scanf("%d", &testcase);

	for (int t = 0; t < testcase; t++) {
		scanf("%d %d", &n, &k);

		memset(d, 0, sizeof(int) * 1001);
		memset(result, 0, sizeof(int) * 1001);
		memset(check, 0, sizeof(int) * 1001);
		memset(order, 0, sizeof(int) * 1001 * 1001);

		for (int i = 1; i <= n; i++)
			scanf("%d", &d[i]);

		for (int i = 0; i < k; i++) {
			scanf("%d %d", &temp1, &temp2);
			order[temp1][temp2] = 1;
		}

		scanf("%d", &dest);

		result[dest] = d[dest];
		bfs.push(dest);

		while (!bfs.empty()) {
			current = bfs.front();
			count = 0;

			for (int i = 1; i <= n; i++) {
				if (order[i][current] == 1) {
					count++;

					if (check[i] == 0) {
						bfs.push(i);
						check[i] = 1;
					}

					if (result[i] < result[current] + d[i])
						result[i] = result[current] + d[i];
				}
			}

			if (count == 0)
				start = current;

			if (!bfs.empty())
				bfs.pop();
		}

		printf("%d\n", result[start]);
	}

	return 0;
}

znxenter 8년 전 0

시작점이 여러개 일수도 있는건가요?

znxenter 8년 전 0

어느 한 노드의 result 값이 변경되었을 때 그 노드보다 앞에 있는 노드도 result 값을 수정해 주어야합니다.

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

문제

문제

출처

ICPC

1005번 질문입니다.

znxenter 8년 전 0

znxenter 8년 전 0

znxenter 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말