글 읽기 - 20%틀렸습니다. 반례가 무엇이 있고 어떤 부분이 잘못됐을까요?

dydsj0920 5년 전 0

저는 기본적으로 목표 건물을 target이라고 지정하고 경로를 최초로 연결된 지점까지 거꾸로 추적하면서

나중에는 연결된 노드가 없는 곳까지 최대치를 계산해 후보로 뽑아 vector<int> ans에 저장하고 그 중 가장 큰 값을 답으로 정했는데요.

반례를 만들어서 해보고 있는데...딱히 못찾았습니다.

어떤 부분이 잘못됐을까요?

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

int time[1001];
bool check[1001];
int d[1001];
vector<vector<int>> node;

int main()
{
	ios_base::sync_with_stdio(false);

	int t;
	cin >> t;

	while (t--) {
		memset(time, 0, sizeof(time));
		memset(check, false, sizeof(check));
		memset(d, 0, sizeof(d));
		node.clear();

		int n, k;
		cin >> n >> k;

		node.resize(n+1);
		for (int i = 1; i <= n; i++) {
			cin >> time[i];
		}
		for (int j = 0; j < k; j++) {
			int u, v;
			cin >> u >> v;
			//node[u].push_back(v);
			node[v].push_back(u);
		}
		int target;
		cin >> target;

		//BFS
		queue<int> q;
		q.push(target);
		d[target] = time[target];
		vector<int> ans;
		while (!q.empty()) {
			int now = q.front();
			check[now] = true;
			q.pop();
			for (int i = 0; i < node[now].size(); i++) {
				int next = node[now][i];
				if (d[next] < d[now] + time[next]) {
					d[next] = d[now] + time[next];
				}
				if (!check[next]) {
					q.push(next);
				}
			}
			if (node[now].size() == 0) {
				ans.push_back(d[now]);
			}
		}
		int max = 0;
		for (int i = 0; i < ans.size(); i++) {
			if (max < ans[i]) {
				max = ans[i];
			}
		}
		cout << max << '\n';
	}
	return 0;
}

djm03178 5년 전 1

단순한 BFS로 풀 수 있는 문제가 아닙니다. 위상 정렬을 사용해야 합니다.

dydsj0920 5년 전 0

@djm03178 반례 찾아주셔서 감사합니다. 다시 시도해보겠습니다.

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

문제

문제

출처

ICPC

20%틀렸습니다. 반례가 무엇이 있고 어떤 부분이 잘못됐을까요?

dydsj0920 5년 전 0

djm03178 5년 전 1

dydsj0920 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말