結果

問題 No.90 品物の並び替え
コンテスト
ユーザー shinwisteria
提出日時 2017-03-28 18:50:04
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,022 ms / 5,000 ms
コード長 1,674 bytes
コンパイル時間 3,709 ms
コンパイル使用メモリ 78,784 KB
実行使用メモリ 123,336 KB
最終ジャッジ日時 2024-07-06 13:27:11
合計ジャッジ時間 7,079 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayList;
import java.util.Scanner;
public class Narabikae {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int N = s.nextInt(),M = s.nextInt();
		int[][] score = new int[N][N];
		for(int i = 0;i < M;i++){
			score[s.nextInt()][s.nextInt()] = s.nextInt();
		}
		s.close();
		ArrayList<Integer> number = new ArrayList<>();
		int maxscore = 0;
		for(int i = 1;i <= N;i++){
			number.add(i);
		}
		ArrayList<ArrayList<Integer>> All = new ArrayList<>();
		for(ArrayList<Integer> b:Permutation(number)){
			All.add(b);
		}
		for(ArrayList<Integer> list:All){
			//System.out.println(list);
		}
		for(ArrayList<Integer> list:All){
			int total = 0;
			for(int i = 0;i < N-1;i++){
				for(int j = i+1;j < N;j++){
					total += score[list.get(i)-1][list.get(j)-1];
				}
			}
			//System.out.println(list + "  " + total);
			maxscore = Integer.max(maxscore, total);
		}
		System.out.println(maxscore);
	}
	static ArrayList<ArrayList<Integer>> Permutation(ArrayList<Integer> list){
		int N = list.size();
		if(N == 1){
			ArrayList<ArrayList<Integer>> p = new ArrayList<>();
			ArrayList<Integer> q = new ArrayList<>();
			q.addAll(list);
			p.add(q);
			return p;
		}
		ArrayList<ArrayList<Integer>> A = new ArrayList<>();
		for(int i = 0;i < N;i++){
			int first = list.get(i);
			ArrayList<Integer> B = new ArrayList<>();
			for(int j = 0;j < N;j++){
				if(j != i){
					B.add(list.get(j));
				}
			}
			//System.out.println(B);
			for(ArrayList<Integer> c:Permutation(B)){
				ArrayList<Integer> d = new ArrayList<>();
				d.add(first);
				d.addAll(c);
				A.add(d);
				//System.out.println(d);
			}
		}
		return A;
	}

}
0