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


    4년 전
0개의 댓글이 있습니다.

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