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;
    }
    


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

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


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