글 읽기 - 10273번 고대 동굴 탐사

wxogus25 8년 전 0

dfs와 메모이제이션을 이용한 방식으로는 풀렸는데

똑같은 식을 사용한 dp로는 풀리지 않네요

어디가 잘못됐나요?

아래는 성공한 코드의 dfs 부분입니다.

int dfs(int now)
{
    int &res=dap[now];

    if(res!=-1)
        return res;
    int i,a;
    res=0;
    a=v[now].size();
    for(i=0;i<a;i++)
    {
        if(res<dfs(v[now][i].first)-v[now][i].second)
        {
            res=dfs(v[now][i].first)-v[now][i].second;
            pass[now]=v[now][i].first;
        }
    }
    res+=value[now];

    return res;
}

#include <iostream>
#include <fstream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <sstream>
#include <map>

using namespace std;

int pass[20011];
long long sum[20011],c[20011];
queue<int> e;
vector<pair<int,int> > v[20011];

void ps(int level, int next)
{
	if(pass[next]==0)
	{
		cout << level << endl;
		while(!e.empty())
		{
			printf("%d ",e.front());
			e.pop();
		}
		cout << next << endl;
		return;
	}
	e.push(next);
	ps(level+1,pass[next]);
}

int main()
{
	int t,n,m,i,j,a,b,cost;
	
	cin >> t;
    fill(sum,sum+20010,0);
	while(t--)
	{
		cin >> n >> m;
		for(i=1;i<=n;i++)
		{
			scanf("%d",&c[i]);
		}
		while(m--)
		{
			scanf("%d %d %d",&a,&b,&cost);
			v[a].push_back(make_pair(b,cost));
		}
		for(i=n;i>=1;i--)
		{
			a=v[i].size();
			for(j=0;j<a;j++)
			{
				if(sum[i]<sum[v[i][j].first]-v[i][j].second)
				{
					sum[i]=sum[v[i][j].first]-v[i][j].second;
					pass[i]=v[i][j].first;
				}
			}
			sum[i]+=c[i];
		}

		cout << sum[1] << " ";
		ps(1,1);
        fill(sum,sum+n+1,0);
        fill(pass,pass+n+1,0);
        fill(c,c+n+1,0);
		for(i=1;i<=n;i++)
		{
			v[i].clear();
		}
	}
}

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

문제

문제

출처

ICPC

10273번 고대 동굴 탐사

wxogus25 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말