안녕하세요
[[problem: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

소스코드

~~~ c++

#include
#include

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;

}

</spoiler>