結果

問題 No.90 品物の並び替え
ユーザー yaoshimaxyaoshimax
提出日時 2015-03-01 23:32:55
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 67 ms / 5,000 ms
コード長 1,278 bytes
コンパイル時間 723 ms
コンパイル使用メモリ 92,508 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-06 06:01:12
合計ジャッジ時間 1,591 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 9 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 8 ms
4,384 KB
testcase_06 AC 7 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 67 ms
4,384 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>

using namespace std;

int main(){
   int N,M;
   cin >> N >> M;
   vector<int> perm;
   for( int i = 0 ; i < N ; i++ ){
      perm.push_back(i);
   }
   vector<pair<int,int> > order[N];
   for( int i = 0 ; i < M ; i++ ){
      int a,b,s;
      cin >> a >> b >> s;
      order[b].push_back(make_pair(a,s));
   }
   int score = 0;
   do{
      int curScore = 0;
      bool appeared[N];
      memset(appeared,false,sizeof(appeared));
      for( int i = 0 ; i < N ; i++ ){
         appeared[perm[i]]=true;
         int p = perm[i];
         for( int j = 0 ; j < (int)order[p].size(); j++ ){
            pair<int,int> pa= order[p][j];
            int prev = pa.first;
            int scr=pa.second;
            if( appeared[prev] == false ){
               curScore+=scr;
            }
         }
      }
      score =max(score,curScore);
   }while(next_permutation(perm.begin(),perm.end()));

   printf("%d\n",score);
   return 0;
}
0