結果

問題 No.357 品物の並び替え (Middle)
コンテスト
ユーザー series_pi
提出日時 2016-04-13 14:32:38
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,875 bytes
コンパイル時間 932 ms
コンパイル使用メモリ 91,020 KB
実行使用メモリ 10,020 KB
最終ジャッジ日時 2024-10-04 07:15:42
合計ジャッジ時間 7,382 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 1 RE * 1 TLE * 1 -- * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:71:34: warning: 'a' may be used uninitialized [-Wmaybe-uninitialized]
   71 |         acc += items[a].w[items[a].next];
      |                                  ^
main.cpp:58:9: note: 'a' was declared here
   58 |     int a, s = 99999;
      |         ^
main.cpp:52:24: warning: 'a' may be used uninitialized [-Wmaybe-uninitialized]
   52 |                 items[a].prev = i;
      |                        ^
main.cpp:34:17: note: 'a' was declared here
   34 |             int a, s = -1;
      |                 ^

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <set>

struct item{
    int next = -1;
    int prev = -1;
    std::map<int, int> v, w;
};

int main(){
    int n, m;
    std::cin >> n >> m;
    std::vector<item> items(n);
    for(int i = 0; i < m; ++i){
        int a, b, s;
        std::cin >> a >> b >> s;
        items[a].v[s] = b;
        items[a].w[b] = s;
    }
    std::set<int> undeterminates;
    for(int i = 0; i < n; ++i){
        int b = items[i].v.rend()->second;
        if(items[b].prev == -1){
            items[i].next = b;
            items[b].prev = i;
        }
        undeterminates.insert(i);
    }
    while(undeterminates.size() > 1){
        auto next_undeterminates = undeterminates;
        for(auto i : undeterminates){
            int a, s = -1;
            for(auto j : undeterminates){
                if(i == j){ continue; }
                int s_ = 0;
                if(items[i].w.find(j) != items[i].w.end()){
                    s_ = items[i].w[j];
                }
                if(s < s_){
                    a = j;
                    s = s_;
                }
            }
            int p = items[i].next, x = 0;
            if(items[i].w.find(p) != items[i].w.end()){
                x = items[i].w[p];
            }
            if(s > x){
                items[i].next = a;
                items[a].prev = i;
                next_undeterminates.erase(i);
            }
        }
        undeterminates = next_undeterminates;
    }
    int a, s = 99999;
    for(auto &i: items){
        int s_ = 0;
        if(i.w.find(i.next) != i.w.end()){
            s_ = i.w[i.next];
        }
        if(s > s_){
            s = s_;
            a = i.next;
        }
    }
    int acc = 0;
    for(int i = 0; i < n - 1; ++i){
        acc += items[a].w[items[a].next];
    }
    std::cout << acc << std::endl;
    return 0;
}
0