timetrip 문제 질문드립니다

  • sangchu
    sangchu

    책에 나와있는대로 벨만-포드와 플로이드 알고리즘 조합해서 풀어봤는데 계속 오답이 발생합니다.
    algospot에서 관련 문제에 대한 testcase 찾아서 전부 돌려봐도 이상한 점은 못찾겠습니다.
    출력 포맷도 확인해 봤지만 이것도 문제는 아닌 것 같습니다.
    제가 놓치는 부분이 뭔지 알려주시면 고맙겠습니다.

    #include <iostream>
    #include <vector>
    #include <cstring>
    
    using namespace std;
    
    const int MAX_V = 100;
    const int INF = 987654321;
    
    int v;
    
    vector<pair<int, int> > adj[MAX_V];
    
    bool reachable[MAX_V][MAX_V];
    
    int bellmanFord (int src, int target)
    {
        vector<int> upper (v, INF);
        upper[src] = 0;
    
        for (int i = 0 ; i < v - 1 ; i++)
            for (int j = 0 ; j < v ; j++)
                for (int k = 0 ; k < adj[j].size() ; k++)
                {
                    int t = adj[j][k].first;
                    int w = adj[j][k].second;
    
                    if (upper[t] > (upper[j] + w))
                        upper[t] = upper[j] + w;
                }
    
        for (int i = 0 ; i < v ; i++)
            for (int j = 0 ; j < adj[i].size() ; j++)
            {
                int t = adj[i][j].first;
                int w = adj[i][j].second;
    
                if (upper[t] > (upper[i] + w))
                    if (reachable[src][i] && reachable[i][target])
                        return -INF;
            }
    
        return upper[target];
    }
    
    int main (int argc, char *argv[])
    {
        int test;
    
        cin >> test;
    
        while (test--)
        {
            int w;
            int first, second;
    
            cin >> v >> w;
    
            for (int i = 0 ; i < MAX_V ; i++)
                adj[i].clear ();
    
            memset (reachable, false, sizeof (reachable));
            for (int i = 0 ; i < v ; i++)
                reachable[i][i] = true;
    
            for (int i = 0 ; i < w ; i++)
            {
                int a, b, c;
                cin >> a >> b >> c;
                adj[a].push_back (make_pair (b, c));
                reachable[a][b] = true;
            }
    
            for (int i = 0 ; i < v ; i++)
                for (int j = 0 ; j < v ; j++)
                    for (int k = 0 ; k < v ; k++)
                        reachable[j][k] |= reachable[j][i] && reachable[i][k];
    
            first = bellmanFord (0, 1);
    
            if (first == INF)
            {
                cout << "UNREACHABLE" << endl;
                continue;
            }
            else if (first == -INF)
                cout << "INFINITY ";
            else
                cout << first << " ";
    
            for (int i = 0 ; i < v ; i++)
                for (int j = 0 ; j < adj[i].size() ; j++)
                    adj[i][j].second = -adj[i][j].second;
    
            second = bellmanFord (0, 1);
    
            if (second == -INF)
                cout << "INFINITY" << endl;
            else
                cout << -second << endl;
        }
    
        return 0;
    }
    


    2년 전
2개의 댓글이 있습니다.
  • sangchu
    sangchu

    자답합니다. unreachable case의 경우 0->1 path가 없으면서 1의 최단 거리가 update되는 경우를 고려하니 통과했습니다.


    2년 전 link
  • 금승원
    금승원

    감사합니다 ㅠ


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