글 읽기 - 어떤 케이스에 대해 틀린 답을 내놓는데 어떤 부분을 더 수정해야 할까요?

creationyun 6년 전 0

생각보다 무엇이 잘못됐는지 발견하기가 어렵네요 ㅜㅜ 도와주세요.

#include <cstdio>
#include <vector>
#include <algorithm>

#define INF 2147483647

using namespace std;

int DP[100001][5];

vector<int> g_tree[100001];
bool visited[100001];
int n;

int DFS(int node, int color) {
    int i, j;
    if (DP[node][color] != -1) return DP[node][color];
    DP[node][color] = color;
    visited[node] = true;
    for (i = 0; i < g_tree[node].size(); i++) {
        int minim = INF;
        if (visited[g_tree[node][i]]) continue;
        for (j = 1; j <= 4; j++) {
            if (color == j) continue;
            if (minim == INF) minim = DFS(g_tree[node][i], j);
            else minim = min(minim, DFS(g_tree[node][i], j));
        }
        DP[node][color] += minim;
    }
    visited[node] = false;
    return DP[node][color];
}

int main()
{
    int i, j;
    int v1, v2;
    int ans = INF;
    scanf("%d", &n);

    for (i = 0; i <= 100000; i++) {
        for (j = 0; j < 5; j++) {
            DP[i][j] = -1;
        }
    }

    for (i = 0; i < n-1; i++) {
        scanf("%d %d", &v1, &v2);
        g_tree[v1].push_back(v2);
        g_tree[v2].push_back(v1);
    }

    for (i = 1; i <= 4; i++) {
        if (ans == INF) ans = DFS(1, i);
        else ans = min(ans, DFS(1, i));
    }

    printf("%d", ans);

    return 0;
}

creationyun 6년 전 0

해결됐습니다.

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

문제

문제

출처

ICPC

어떤 케이스에 대해 틀린 답을 내놓는데 어떤 부분을 더 수정해야 할까요?

creationyun 6년 전 0

creationyun 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말