글 읽기 - 반례를 못찾겠습니다.

gusdnr9875 5년 전 0

dfs랑 dp를 이용해서 풀었습니다. 어떤 반례가 있고 어떻게 해결해야할까요?

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector <int> arr[1001];
bool visited[1001];
int d[1001] = { 0 };
int dp[1001] = { 0 };
int t = 0, n = 0, k = 0, w = 0;
int x = 0, y = 0, maxx = 0;

void dfs(int num, int sum) {
	if (num == w) {
		if (maxx < sum) maxx = sum;
		return ;
	}
	

	dp[num] = sum;

	for (int i = 0; i < arr[num].size(); i++)
	{
		if (visited[arr[num].at(i)] == 0&& (d[arr[num].at(i)] + sum)>=dp[arr[num].at(i)]) {
			visited[arr[num].at(i)] = 1;
			dfs(arr[num].at(i), d[arr[num].at(i)] + sum);
			visited[arr[num].at(i)] = 0;
		}
	}


	return;
}

int main() {
	cin >> t;

	while (t--) {
		cin >> n >> k;

		for (int i = 1; i <= n; i++) cin >> d[i]; //건물의 개수 입력 
		for (int i = 1; i <= k; i++) { cin >> x >> y; arr[x].push_back(y); }
		cin >> w;

		for (int i = 1; i <= n; i++) visited[i] = 0, dp[i] = 0;
		maxx = 0;
		dfs(1, d[1]);
		cout << maxx << '\n';
	}
}

djm03178 5년 전 1

https://www.acmicpc.net/board/...

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

문제

문제

출처

ICPC

반례를 못찾겠습니다.

gusdnr9875 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말