結果

問題 No.357 品物の並び替え (Middle)
ユーザー series_piseries_pi
提出日時 2016-04-13 14:32:38
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,875 bytes
コンパイル時間 996 ms
コンパイル使用メモリ 90,480 KB
実行使用メモリ 10,268 KB
最終ジャッジ日時 2024-04-15 00:40:34
合計ジャッジ時間 7,646 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 RE -
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
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;
      |                 ^
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;
      |         ^

ソースコード

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