JAEHACHERRY 문제의 오답을 도저히 못 찾겠습니다 ㅠㅠ

  • porcosedol
    porcosedol

    JAEHACHERRY
    재하와 버찌씨 여덟개 문제를 별로 어렵지 않게 생각했는데 오답만 내다가 거의 1년이 다되가고 있습니다. 첨부한 코드는 bfs 탐색해서 한 점에서 다른 점까지 가격 비율을 구했는데 오답입니다. 아.. 어디에 버그가 있을까요? 제발 도와주세요.

    #include <iostream>
    #include <string>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <algorithm>
    using namespace std;
    
    
    const int MAX_WIDTH = 8;
    double board[8][8];
    vector<double> make_relations(int size) {
        vector<bool> visited(size, false);
        vector<double> relations(size);
        relations[0] = 1;
        visited[0] = true;
        queue<int> q;
        q.push(0);
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            for (int i = 0; i < size; i++) {
                if (visited[i] == false && board[p][i] > 0) {
                    visited[i] = true;
                    relations[i] = relations[p] * board[p][i];
                    q.push(i);
                }
            }
        }
        return relations;
    }
    
    int main()
    {
        //freopen("sample_input.txt", "r", stdin);
        //setbuf(stdout, NULL);
        int test_num;
        cin >> test_num;
        while (test_num--) {
            for (int i = 0; i < MAX_WIDTH; i++) {
                for (int j = 0; j < MAX_WIDTH; j++) {
                    board[i][j] = 0;
                }
            }
            map<int, string> id_to_name;
            map<string, int> name_to_id;
            int trade_num;
            cin >> trade_num;
            int id = 0;
            for (int i = 0; i < trade_num; i++) {
                string name1, name2;
                double val1, val2;
                cin >> name1 >> val1 >> name2 >> val2;
                int src, target;
                if (name_to_id.count(name1) > 0) {
                    src = name_to_id[name1];
                }
                else {
                    src = id;
                    name_to_id[name1] = id;
                    id_to_name[src] = name1;
                    id++;
                }
                if (name_to_id.count(name2) > 0) {
                    target = name_to_id[name2];
                }
                else {
                    target = id;
                    name_to_id[name2] = id;
                    id_to_name[target] = name2;
                    id++;
                }
                board[src][target] = val2 / val1;
                board[target][src] = val1 / val2;
            }
            auto relations = make_relations(name_to_id.size());
            vector<pair<double, string>> v;
            for (int i = 0; i < relations.size(); i++) {
                v.push_back({ relations.at(i), id_to_name.at(i) });
            }
            sort(v.begin(), v.end());
            for (auto p : v)
                cout << p.second << " ";
            cout << endl;
        }
    
        return 0;
    }
    
    {{Ws8zXTvOvJ4h3HGk}}
    

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

    DFS, BFS, 다익스트라, 벨만포드, 플로이드로 전부 풀어보고, 부동소숫점 차이인가 싶어서 분수 클래스까지 만들었었는데도 저도 못풀었네요. ㄷㄷ


    9년 전 link
  • porcosedol
    porcosedol

    ㅠㅠ


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