TIMETRIP 문제 계속 오답 왜 그런지 알려주세요~~

  • wingjoy
    wingjoy

    안녕하세요
    TIMETRIP 문제를 일주일째 풀고 있습니다 --;;
    왜 계속 오답이 나오는지 알 수 없어서 문의 드립니다.
    Test case 와 그에 출력(답)을 알 수 있나요?
    알고리즘상의 문제가 있는건가요?

    현재 은하(Node)에서 다음 은하(sub node)의 min max 를 취합하는 방식으로 구현 했으며, infinity를 따로 취합 하도록 했습니다.
    infinity 가 되는지 여부는 웜홀의 목적지가 이전 출발지가 될때 시간의 합을 계산 하도록 했습니다.

    하나의 은하(Node)에서 출발하여 다른 은하로 가는 윔홀(edge)을
    linked list 형식으로 Node에 link된 edge를 순차적으로 search 할 수 있도록 했으며, 한번 계산된 edge는 중복해서 가보지 않도록 Node에 최종 min, max를 저장 처리 했습니다.

    Test case

    1
    4 6
    0 1 1
    0 2 100
    2 3 -1
    3 2 -1
    2 3 1000
    3 1 -10

    3
    4 4
    0 1 1
    0 2 100
    2 3 1
    3 2 1
    4 4
    0 1 1
    0 2 100
    2 3 -1
    3 2 -1
    4 5
    0 1 1
    0 2 100
    2 3 -1
    3 2 -1
    2 3 1000

    1
    7 8
    0 2 1
    2 1 1
    2 6 1
    6 7 1
    7 2 1
    2 4 1
    4 5 -4
    5 2 1

    3
    4 5
    0 2 1
    2 3 0
    2 3 2
    3 2 -1
    2 1 1
    4 5
    0 2 1
    2 3 0
    2 3 2
    3 2 0
    2 1 1
    4 5
    0 2 1
    2 3 0
    2 3 2
    3 2 1
    2 1 1

    1
    6 7
    0 1 10
    0 2 2
    2 3 3
    2 4 4
    3 5 5
    4 5 4
    5 0 -1

    소스코드

    #include <stdio.h>
#include <string.h>


struct edge {
    int path_len;
    int start_node;
    int end_node;
    struct edge* parent;
    struct edge* child;
    struct edge* next;
    int calced;
};

struct node {
    int min;
    int max;
    int p_infinity;
    int n_infinity;
    int reached;
    struct edge* src_edge;
};

struct node node_array[100];
struct edge edge_array[1000];

/*
return : changed current node
   */
struct node* find_route(struct node* curr_node, struct edge* parent, int depth)
{
    struct node* p_node;
    struct edge* p_edge;
    struct edge* p_parent;
    int sub_min = 0;
    int sub_max = 0;
    int i;
    int infinity_len = 0;
    int ret = 0;

    p_node = curr_node;

    if (parent && parent->end_node == 1) { /* Final Destination */
        curr_node->reached = 1;
    }
    if (!p_node->src_edge) {
        return curr_node;
    }

    if (parent) {
        int loop_detected = 0;
        p_parent = parent;
        for (; p_parent;) {
            infinity_len += p_parent->path_len;
            if (p_parent->start_node == parent->end_node) {
                loop_detected = 1;
                break;
            }
            p_parent = p_parent->parent;
        }
        if (loop_detected) { /* Found loop path */
            int loop_edge_path_len;
            int p_infinity = 0;
            int n_infinity = 0;

            if (infinity_len > 0) {
                p_infinity = 1;
            } else if (infinity_len < 0) {
                n_infinity = 1;
            }
            p_node = &node_array[p_parent->start_node];
            for (p_edge = p_node->src_edge; p_edge; ) {
                if (!p_edge->calced) {
                    if (p_edge->end_node == p_parent->end_node) {
                        loop_edge_path_len = infinity_len - p_parent->path_len + p_edge->path_len;
                        if (loop_edge_path_len > 0) {
                            p_infinity = 1;
                        } else if (loop_edge_path_len < 0) {
                            n_infinity = 1;
                        }
                    }
                }
                if (p_edge->next) {
                    p_edge = p_edge->next;
                } else {
                    break;
                }
            }
            for (;;) {
                p_node = &node_array[p_parent->start_node];
                if (p_infinity) {
                    p_node->p_infinity = 1;
                }
                if (n_infinity) {
                    p_node->n_infinity = 1;
                }
                if (!p_parent->child)
                    break; /* self worm-hole */
                p_parent = p_parent->child;
            }
            return curr_node;
        }
    }

    for ( p_edge = curr_node->src_edge; p_edge; ) {

        if (p_edge->calced) {
            if (p_edge->next) {
                p_edge = p_edge->next;
            } else {
                break;
            }
            continue;
        }
        p_edge->calced = 1;
        p_edge->parent = parent;
        if (parent)
            parent->child = p_edge;

        p_node = &node_array[p_edge->end_node];
        p_node->p_infinity = curr_node->p_infinity;
        p_node->n_infinity = curr_node->n_infinity;
        p_node = find_route(p_node, p_edge, depth + 1);

        if (p_node->reached) {
            sub_min = p_edge->path_len + p_node->min;
            sub_max = p_edge->path_len + p_node->max;

            if (!curr_node->reached) {
                curr_node->min = sub_min;
                curr_node->max = sub_max;
            }
            else {
                if (curr_node->min > sub_min) {
                    curr_node->min = sub_min;
                }
                if (curr_node->max < sub_max) {
                    curr_node->max = sub_max;
                }
            }
            curr_node->reached = 1;
            if (p_node->n_infinity)
                curr_node->n_infinity = 1;
            if (p_node->p_infinity)
                curr_node->p_infinity = 1;
        }
        if (parent)
            parent->child = 0;
        p_edge = p_edge->next;
    }
    return curr_node;
}

int main(void)
{

    int test_cnt;
    int i, j;
    int V, W;
    struct node* p_node;
    struct edge* p_edge;
    int reached;

    scanf("%d", &test_cnt);

    for (i = 0; i < test_cnt; i++) {
        int a, b, d;
        scanf("%d %d", &V, &W);
        memset(&node_array[0], 0, sizeof(node_array));
        memset(&edge_array[0], 0, sizeof(edge_array));

        for (j = 0; j < W; j++) {
            scanf("%d %d %d", &a, &b, &d);
            edge_array[j].start_node = a;
            edge_array[j].end_node = b;
            edge_array[j].path_len = d;
        }

        for (j = 0; j < W; j++) {
            int st_node;
            int ed_node;

            st_node = edge_array[j].start_node;
            p_edge = node_array[st_node].src_edge;

            if (p_edge != NULL ) {
                for ( ; p_edge->next != NULL; ) {
                    p_edge = p_edge->next;
                }
                p_edge->next = &edge_array[j];
                p_edge = p_edge->next;
            } else {
                node_array[st_node].src_edge = &edge_array[j];
                p_edge = node_array[st_node].src_edge;
            }
        }
        p_node = &node_array[0];

        find_route(p_node, 0, 0);

        if ( p_node->reached) {
            if (p_node->n_infinity && p_node->p_infinity) {
                printf("INFINITY INFINITY\n");
            } else if (p_node->n_infinity) {
                printf("INFINITY ");
                printf("%d\n", p_node->max);
            } else if (p_node->p_infinity) {
                printf("%d ", p_node->min);
                printf("INFINITY\n");
            } else {
                printf("%d ", p_node->min);
                printf("%d\n", p_node->max);
            }
        } else {
            printf("UNREACHABLE\n");
        }
    }
    return 0;
}


    10년 전
1개의 댓글이 있습니다.
  • wingjoy
    wingjoy

    test case 미공개 원칙에 고생은 했지만 정답을 많이 생각하면서 찾을 수 있었습니다 ^^


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.