Trabalho de Grafos

Ministério da Educação Instituto Federal de Goiás Campus Luziânia Departamento de Áreas Acadêmicas Estrutura de Dados II Trabalho Grafos Questão 1 100 Ponto Roteadores Bruno é responsável por configurar os roteadores de uma empresa Os roteadores transmitem os dados entre si através dos cabos de Internet Os dados transmitidos podem trafegar por uma ou mais rotas para serem entregues ao destinatário O preço dos cabos de rede utilizados nos roteadores da empresa pode chegar a ser muito caro e a empresa precisa cortar gastos Pensando nisso a empresa decidiu fazer algumas alterações na infraestrutura de redes Bruno deve modificar a infraestrutura de redes da empresa de forma com que todos os roteadores consigam transmitir dados entre si e exista somente uma rota entre cada par de roteadores economizando o máximo possível de cabos de internet Sua tarefa é descobrir qual será o custo total com cabos que a empresa terá após as modificações feitas por Bruno A figura abaixo mostra a a infraestrutura de redes atual e b a infraestrutura de redes após as modificações feitas Entradas A primeira linha é composta por dois inteiros R 3 R 60 e C R C 200 representando respectivamente a quantidade de roteadores e a quantidade de cabos de Internet utilizados atualmente Seguem C linhas cada uma contendo três inteiros V 1 V R W 1 W R e P 1 P 10000 sendo V e W um par de roteadores que estão conectados por um cabo de internet e P o preço do cabo de internet utilizado Saída Seu programa deve imprimir um único valor inteiro que presenta o custo total que a empresa gastará com cabos após as modificações Ministério da Educação Instituto Federal de Goiás Campus Luziânia Departamento de Áreas Acadêmicas Estrutura de Dados II Exemplo de Entrada Exemplo de Saída 7 12 1 3 6 1 4 9 2 3 17 2 5 32 2 7 27 3 4 11 3 5 4 4 5 3 4 6 19 5 6 13 5 7 15 6 7 5 48 Observações Importantes O programa deverá ser implementado na linguagem Java Os trabalhos deverão ser feitos de forma individual Elabore um relatório que discuta em linhas gerais a estrutura lógica usada para desenvolver o trabalho O relatório deve permitir compreender o trabalho sem a necessidade do código A presença de comentários no código ajuda na compreensão e será considerada na nota Serão considerados 3 aspectos para a nota final do trabalho Funcionamento do programa 30 Código 40 Relatório 30 São anulados aqueles trabalhos nos quais forem detectados quaisquer tipos de cópias ou plágio não importa a origem A data de entrega deste trabalho será 12092024