글 읽기 - 2157 여행 DP 질문입니다

exqt 8년 전 1

d[x][y] = 현재 도시 x에서 y번 이동했을 때 최대치

v[x][y] = x -> y 경로의 가중치

점화식은 d[i][k] = max(d[i][k], d[j][k - 1] + v[j][i]) 입니다

없는 경로는 -1을 넣어주어 예외처리 하였고 답은 d[n][i] (i <= m-1) 중 가장 큰 것을 골랐는데 잘 안나오네요

문제에서 N=1인 경우와 가는 경로가 없을때 문제가 되나요?

#include <iostream>
#include <fstream>
#include <map>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
#define in cin
#define out cout
#define LL unsigned long long
#define pii pair<int, int>
#define INF 1000000007
 
int d[301][301]; // 도시, 남은횟수
int v[301][301]; // x -> y
 
int main()
{
    int n, m, k; in >> n >> m >> k;
    memset(d, -1, 301 * 301);
    memset(v, -1, 301 * 301);
 
    while (k--)
    {
        int x, y, w; in >> x >> y >> w;
        v[x][y] = max(v[x][y], w); 
    }
 
    d[1][0] = 0;
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j < i; j++)
        {
            for (int k = 1; k <= m-1; k++)
            {
                if (v[j][i] != -1 && d[j][k - 1] != -1)
                {
                    d[i][k] = max(d[i][k], d[j][k - 1] + v[j][i]);
                }
            }
        }
    }
 
    int res = 0;
    for (int i = 1; i <= m-1; i++) res = max(res, d[n][i]);
    out << res;
 
    return 0;
}

exqt 8년 전 0

감사합니다! 어이없는 실수를 했네요 ㅋㅋ

다음부턴 그냥 fill쓰는걸로..

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

문제

문제

출처

ICPC

2157 여행 DP 질문입니다

exqt 8년 전 1

exqt 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말