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

wiz 8년 전 0

출발지는 건설하고자 하는 건물번호입니다. 즉, BFS를 역순으로 돌립니다.

D라는 배열에 (전에 방문한 건물 까지의 최대거리) + (현재 건물 소요 시간) 를 통해 갱신하고

global maximum 을 출력합니다.

예제는 맞게 나오는데, 제출시 틀렸다고 나오네요. 논리적으로 어떤 점에서 오류가 있는 것인지 알고 싶습니다.

답변 부탁드립니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;

int N, K;
vector<vector<int> > adj;
vector<int> D, v, visit;

int ret;
void bfs(int start) {
	visit = vector<int>(N, -1);
	D[start] = ret = v[start];
	visit[start] = 0;
	queue<int> q; q.push(start);

	while (!q.empty()) {
		int here = q.front(); q.pop();
		for (int i = 0; i < adj[here].size(); ++i) {
			int there = adj[here][i];
			if (visit[there] == -1) {
				visit[there] = 1;
				q.push(there);
			}
			D[there] = max(D[there], D[here] + v[there]);    //갱신
			ret = max(ret, D[there]);
		}
	}
}
int main() {

	int c; cin >> c; while (c--) {
		cin >> N >> K;
		adj = vector<vector<int> >(N);
		D = v = vector<int>(N);

		int a, b;
		for (int i = 0; i < N; ++i)
			scanf("%d", &v[i]);
		while (K--) {
			scanf("%d%d", &b, &a);
			adj[--a].push_back(--b);
		}
		int t; cin >> t;
		bfs(--t);
		cout << ret << endl;
		
	}
	return 0;
}

ca00229 8년 전 2

1
4 4
10 1 100 10
1 2
2 3
2 4
3 4
4

121이 나와야 되는데, 111이 나옵니다.

2번 건물이 만들어진 후에 만들 수 있는 건물을 모두 검사한 뒤에 2번을 큐에 집어넣어야 되는데, 그렇지 않아서 그런거 같네요.

위상 정렬에 대해 찾아보시면 도움이 될거 같아요.

wiz 7년 전 0

위상 정렬에 대해서 다시 공부한 뒤 한달이 지나서야 풀었네요.

힌트주셔서 정말 감사합니다. 이제서야 답변다네요 ㅠ

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

문제

문제

출처

ICPC

1005번 질문입니다.

wiz 8년 전 0

ca00229 8년 전 2

wiz 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말