Promises 질문

  • taso
    taso

    https://algospot.com/judge/problem/read/PROMISES
    음.. Jongman book에 나온대로 한 것 같은데 안되네요 ㅠㅠ..
    인터넷에 떠돌아다니는 소스코드를 4개?시험해봤는데 그 코드들도 전부 오답으로 뜨더라고요요.
    혹시 어느 부분이 문제인지 알 수 있을까요?
    소스코드를 대략 설명하면, existing에 floyd알고리즘을 이용해서 distance를 저장했어요.
    그 다음, 새로운 고속도로(n1,n2)가 추가될 때마다,
    dist(i,j)를 dist(i,n1)+weight+dist(n2,j), dist(i,n2)+weight+dist(n1,j)와 비교해서 업데이트했고요.
    업데이트안되면 쓸모없는 고속도로라고 생각했습니다.

    #include<iostream>
    #include<vector>
    #define INF 0x26543210
    using namespace std;
    
    int numExisting, numWillBuild, V;
    vector< vector<int> > existing;
    vector< pair<int,int> > willBuildD;
    vector<int> willBuildW;
    
    void floyd() {
        for (int k=0; k<V; k++) {
            for (int i=0; i<V; i++) {
                for (int j=0; j<V; j++) {
                    existing[i][j] = min(existing[i][j], existing[i][k]+existing[k][j]);
                }
            }
        }
    }
    
    bool tryUpdate(int n1, int n2, int weight) {
        bool updated = false;
        if (existing[n1][n2]<=weight) return false;
        for (int i=0; i<V; i++) {
            for (int j=0; j<V; j++) {
                if (existing[i][n1] + weight + existing[n2][j] < existing[i][j]) {
                    existing[i][j] = existing[i][n1] +weight + existing[n2][j];
                    updated = true;
                }
                if (existing[i][n2] + weight + existing[n1][j] < existing[i][j]) {
                    existing[i][j] = existing[i][n2] +weight + existing[n1][j];
                    updated = true;
                }
            }
        }
        return updated;
    }
    
    int solve() {
        int useless = 0;
        floyd();
        for (int i=0; i<willBuildD.size(); i++) {
            pair<int,int> nPair = willBuildD[i];
            int weight = willBuildW[i];
            if (!tryUpdate(nPair.first, nPair.second, weight)) {
                useless++;
            }
        }
        return useless;
    }
    
    int main() {
        int C, n1, n2, weight;
        vector<int> sols;
        cin >> C;
        for (int i=0; i<C; i++) {
            cin >> V >> numExisting >> numWillBuild;
            existing.clear();
            existing.resize(V, vector<int>(V, INF));
            for (int j=0; j<V; j++)
                existing[j][j] = 0;
            for (int j=0; j<numExisting; j++) {
                cin >> n1 >> n2 >> weight;
                existing[n1][n2] = weight;
                existing[n2][n1] = weight;
            }
            willBuildD.clear();
            willBuildD.resize(numWillBuild);
            willBuildW.clear();
            willBuildW.resize(numWillBuild);
            for (int j=0; j<numWillBuild; j++) {
                cin >> n1 >> n2 >> weight;
                willBuildD[j] = pair<int,int>(n1, n2);
                willBuildW[j] = weight;
            }
            sols.push_back(solve());
        }
        for (int i=0; i<C; i++) {
            cout << sols[i] <<endl;
        }
    }
    

    1주 전
2개의 댓글이 있습니다.
  • kriii
    kriii

    그냥 눈에 보이는 문제점을 언급해 보겠습니다.


    같은 두 도시를 연결하는 도로가 하나라는 언급이 없습니다.


    1주 전 link
  • taso
    taso

    ..그렇군요..

    문제풀기 위한 세팅부분에서 이런 함정이 있을 수 있네요 ㄷㄷ
    좋은 경험했습니다.


    1주 전 link
  • 댓글을 남기시려면 로그인하세요.