(SPOJ) 11651 - Banda - Solução 1

1ª Solução tentada: não eficiente.
Não é necessário o vetor, uma vez que a última afinidade é a maior. Com isso também não é necessário o Array.sort().
É possível tratar diferente os casos especiais, sem a necessidade de vários ifs.

import java.io.*;
import java.util.*;

class Main {
    class No {
        public int no1;
        public int no2;
        public int no3;
        public int afinidade;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main processando = new Main();
        processando.processa();
       
        System.exit(0);
    }
   
    void processa() throws NumberFormatException, IOException {
        String line = "";
       
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        line = br.readLine();
        StringTokenizer tokenizer = new StringTokenizer(line);
        int qteMusicos = Integer.valueOf(tokenizer.nextToken());
        int qtePares = Integer.valueOf(tokenizer.nextToken());

        int[][] matrizAdj = new int[qteMusicos][qteMusicos];
       
        if (qtePares < 3) {
            if (qtePares == 0) {
                System.out.println("1 2 3");
            }
            else if (qtePares == 1) {
                line = br.readLine();
                tokenizer = new StringTokenizer(line);
                int musico1 = Integer.valueOf(tokenizer.nextToken());
                int musico2 = Integer.valueOf(tokenizer.nextToken());
                int afinidade = Integer.valueOf(tokenizer.nextToken());
               
                for (int i = 0; i < qteMusicos; i++) {
                    if (i != (musico1-1) && i != (musico2-1)) {
                        System.out.println(musico1 + " " + musico2 + " " + (i+1));
                        break;
                    }
                }
            }
            else if (qtePares == 2) {
                line = br.readLine();
                tokenizer = new StringTokenizer(line);
                int musico1 = Integer.valueOf(tokenizer.nextToken());
                int musico2 = Integer.valueOf(tokenizer.nextToken());
                int afinidade = Integer.valueOf(tokenizer.nextToken());
               
                line = br.readLine();
                tokenizer = new StringTokenizer(line);
                int musico3 = Integer.valueOf(tokenizer.nextToken());
                int musico4 = Integer.valueOf(tokenizer.nextToken());
                afinidade = Integer.valueOf(tokenizer.nextToken());
               
                if (musico3 != musico1 && musico3 != musico2) {
                    System.out.println(musico1 + " " + musico2 + " " + musico3);
                }
                else if (musico4 != musico1 && musico4 != musico2) {
                    System.out.println(musico1 + " " + musico2 + " " + musico4);
                }
                else {
                    for (int i = 0; i < qteMusicos; i++) {
                        if (i != (musico1-1) && i != (musico2-1)) {
                            System.out.println(musico1 + " " + musico2 + " " + i);
                            break;
                        }
                    }
                }
            }
        }
        else {
            for (int i = 0; i < qtePares; i++) {
                line = br.readLine();
                tokenizer = new StringTokenizer(line);
                int musico1 = Integer.valueOf(tokenizer.nextToken());
                int musico2 = Integer.valueOf(tokenizer.nextToken());
                int afinidade = Integer.valueOf(tokenizer.nextToken());
               
                matrizAdj[musico1-1][musico2-1] = afinidade;
                matrizAdj[musico2-1][musico1-1] = afinidade;
            }
               
            No[] nos = new No[100000];
           
            for (int i = 0; i < 100000; i++) {
                nos[i] = new No();
            }
           
            int contador = 0;
            int afinidadeTmp = 0;
            int maior = -1;
            for (int i = 0; i < qteMusicos; i++) {
                for (int j = 0; j < qteMusicos; j++) {
                    if (matrizAdj[i][j] > 0) {
                        for (int k = 0; k < qteMusicos; k++) {
                            afinidadeTmp = matrizAdj[i][j]+matrizAdj[i][k]+matrizAdj[j][k];
                            if (k != i && matrizAdj[j][k] > 0 && afinidadeTmp > maior) {
                                nos[contador].no1 = i;
                                nos[contador].no2 = j;
                                nos[contador].no3 = k;
                                nos[contador].afinidade = afinidadeTmp;
                                contador++;
                                maior = afinidadeTmp;
                            }
                        }
                    }
                }
            }
             
            Arrays.sort(nos, 0, contador, new Comparator<No>() {
                @Override
                public int compare(No n1, No n2)
                {
                    if (n1.afinidade < n2.afinidade) {
                        return +1;
                    }
                    else if (n1.afinidade == n2.afinidade) {
                        return 0;
                    }
                    else {
                        return -1;
                    }
                }
            });
       
            System.out.println((nos[0].no1+1) + " " + (nos[0].no2+1) + " " + (nos[0].no3+1));
        }
              
        return;
    }
}