글 읽기 - dp로 풀 수 없는 문제인가요?

p_ce1052 3년 전 0

한 지점에서 1번 지점을 통과하지 않고는 다시 그 점으로 돌아올 수 없다 - > 사이클이 없다 -> 특정 지점에서 1번 지점으로 가는 최대 거리를 dp로 계산할 수 있다 라고 생각하고 각 지점에서 1번으로 가는최대 거리를 저장하고 경로를 추적했습니다. 반례가 있을까요?

어디가 잘못되었나요?

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
typedef pair<int,int> pi;
vector<pi>graph[1005];
int dp[1005];
int f(int curr,bool fin){ //특정 지점에서 1번 점으로 가는 최대 거리 
	if(fin && curr == 1) return 0; //도착점 1번이면 0을 반환
	int&ret = dp[curr];
	if(~ret) return ret;
	ret = 0;
	for(int i=0; i<graph[curr].size(); i++){
		int next = graph[curr][i].first;
		int d = graph[curr][i].second;
		ret = max(ret,f(next,true)+d);
	}
	return ret;
}
int main(){
	memset(dp,-1,sizeof(dp));
	int n,m;
	cin>>n>>m;
	while(m--){
		int a,b,d;
		cin>>a>>	b>>d;		
		graph[a].push_back(pi(b,d));
	}
	cout<<f(1,false)<<'\n';
	int curr = 1;
	int maxd = 0;
	cout<<curr<<" ";
	while(1){
		for(int i=0; i<graph[curr].size(); i++){
			int next = graph[curr][i].first;
			if(maxd<dp[next]){
				curr = next;
				maxd = dp[next];
			}
		}
		cout<<curr<<" ";
		maxd = 0;
		if(curr==1) break;
	}
} 

pichulia 3년 전 2

DP로 잘 풀립니다.

경로 복원하는 부분을 손봐보세요.

6
3 1
4 1
2 1000
4 1000
5 1
1 1

Answer:
2002
2 4 5 1


----

3
2 1
3 1
3 9

Answer:
9
3

p_ce1052 3년 전 0

2번째 케이스로 주신 그래프가 1로 돌아오는 경로가 없는데 이런 경우도 가능한가요?

p_ce1052 3년 전 0

38번째 줄에서 비교하는 도중에 curr이 바뀌는 것이 문제같아서 임의로 temp변수를 잡고 최댓값을 구한 후에 curr = temp로 갱신했는데도 여전히 틀리게 되네요

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

문제

문제

출처

ICPC

dp로 풀 수 없는 문제인가요?

p_ce1052 3년 전 0

pichulia 3년 전 2

p_ce1052 3년 전 0

p_ce1052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말