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

Solução eficiente

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);
    }

    int pos;

    int leproximo(String line) {
        int n = 0;
        while (line.charAt(pos) == ' ') {
            pos++;
        }
        for ( ; pos < line.length() && line.charAt(pos) != ' '; pos++) {
            n = n*10 + line.charAt(pos) - '0';
        }
        return n;
    }

    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];

        for (int i = 0; i < qtePares; i++) {
            line = br.readLine();
            pos = 0;
            int musico1 = leproximo(line);
            int musico2 = leproximo(line);
            int afinidade = leproximo(line);

            matrizAdj[musico1-1][musico2-1] = afinidade;
            matrizAdj[musico2-1][musico1-1] = afinidade;
        }
       
        No melhor = new No();

        int afinidadeTmp = 0;
        int maior = -1;
        for (int i = 0; i < qteMusicos; i++) {
            for (int j = i+1; j < qteMusicos; j++) {
                int aij = matrizAdj[i][j];
                for (int k = j+1; k < qteMusicos; k++) {
                    afinidadeTmp = aij + matrizAdj[i][k] + matrizAdj[j][k];
                    if (afinidadeTmp > maior) {
                        melhor.no1 = i;
                        melhor.no2 = j;
                        melhor.no3 = k;
                        maior = afinidadeTmp;
                    }
                }
            }
        }
         
          System.out.println((melhor.no1+1) + " " + (melhor.no2+1) + " " + (melhor.no3+1));
     
        return;
    }
}