TIMETRIP 문제에 테스트 케이스 추가를 요청합니다.

  • jw950310
    jw950310

    안녕하세요.
    TIMETRIP 문제에 테스트 케이스 추가를 요청합니다.

    추가해야 하는 테스트 케이스는 다음과 같습니다. (은하계 4개, 웜홀 3개)

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

    추가해야 하는 이유는 다음과 같습니다.

    • 이 문제의 함정은, 음수 사이클이 존재한다고 1번 은하계까지의 거리가 항상 음의 무한대는 아니다입니다. 시작점부터 끝점까지의 최단 경로 안에 음수 사이클이 존재해야 최단 거리가 음의 무한대입니다. 따라서, 책에서는 |V|번째 완화 순환 때 완화하는 간선이 시작점부터 끝점까지의 최단 경로 안에 있는지를 확인하고, 있다면 음의 무한대를 없다면 upper[1]을 리턴했습니다.

    • 저는 목적지를 포함하는 음수 사이클이 존재하지만 시작점과 목적지가 이어지지 않은 경우를 먼저 처리하여 UNREACHABLE을 출력한 뒤, 그 외에 음수 사이클이 존재하는 경우(음수 사이클이 존재하지만 목적지를 포함하지 않거나, 시작점과 목적지가 이어져있음)는 음의 무한대를 리턴했습니다.

    • 하지만 제 코드는 시작점과 목적지가 이어져있고, 시작점과 목적지를 모두 포함하지 않는 음수 사이클이 존재하는 경우에도 음의 무한대를 리턴할 것입니다.

    아래는 저의 코드이며, 위의 테스트 케이스에 대하여 INFINITY 1을 출력합니다. (정답은 1 1)
    현재 제 코드로 TIMETRIP을 통과한 상태입니다.

    #include <bits/stdc++.h>
    using namespace std;
    int v, w;
    vector<pair<int, int>> graph[101];
    int upperChange[101], lowerChange[101];
    int64_t upper[101], lower[101];
    int main()
    {
        int tc;
        cin >> tc;
        while (tc--)
        {
            cin >> v >> w;
            for (int i = 0; i < v; i++)
            {
                graph[i].clear();
                upper[i] = INT_MAX;
                lower[i] = -INT_MAX;
            }
            memset(upperChange, -1, sizeof upperChange);
            memset(lowerChange, -1, sizeof lowerChange);
            for (int i = 0; i < w; i++)
            {
                int a, b, d;
                cin >> a >> b >> d;
                graph[a].push_back(make_pair(b, d));
            }
            upper[0] = 0;
            lower[0] = 0;
            bool upper_updated, lower_updated;
            for (int i = 0; i < v; i++)
            {
                upper_updated = false;
                lower_updated = false;
                for (int j = 0; j < v; j++)
                {
                    for (int k = 0; k < graph[j].size(); k++)
                    {
                        pair<int, int> edge = graph[j][k];
                        if (upper[edge.first] > upper[j] + edge.second)
                        {
                            upper[edge.first] = upper[j] + edge.second;
                            upperChange[edge.first] = j;
                            upper_updated = true;
                        }
                        if (lower[edge.first] < lower[j] + edge.second)
                        {
                            lower[edge.first] = lower[j] + edge.second;
                            lowerChange[edge.first] = j;
                            lower_updated = true;
                        }
                    }
                }
            }
            if (upper[1] >= INT_MAX - 1000 * v)
            {
                cout << "UNREACHABLE" << endl;
                continue;
            }
            else if (upper_updated)
            {
                cout << "INFINITY ";
            }
            else
            {
                cout << upper[1] << " ";
            }
    
            if (lower_updated)
            {
                cout << "INFINITY\n";
            }
            else
            {
                cout << lower[1] << "\n";
            }
        }
    }
    


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