Você e seus amigos irão criar uma nova loja virtual. Para competir com tantas empresas existentes no mercado, além de vender seus produtos sempre com preços justos — sem propagandas enganosas — vocês precisam de algum diferencial. Primeiro, decidiram que irão realizar entregas super rápidas nas cidades que atenderem, desbancando a concorrência. Mas, o mais importante, todos os clientes serão tratados igualmente e com justiça: vocês não querem discriminar os clientes fora das grandes cidades.

Para poder realizar as entregas rapidamente, é imprescindível a construção de centros de distribuição. Assim, quando um cliente realiza uma compra online, o produto já deve estar disponível no centro de distribuição mais próximo da cidade de entrega. A distância de uma cidade até o centro de distribuição mais próximo é a distância de atendimento dessa cidade. Quanto menor for a distância de atendimento de uma cidade, mais rapidamente ela será atendida.

Com escassos recursos em caixa, só é possível construir dois centros de distribuição para atender todas as cidades na área de atuação. O problema é decidir em que cidades instalar esses dois centros. Como a missão da nova empresa é atender todos os clientes de maneira igualitária, vocês decidiram que os centros serão instalados nas cidades de forma a minimizar a maior distância de atendimento de uma cidade.

Vejamos um exemplo. Na figura abaixo, estão destacadas as cidades a serem atendidas pela loja virtual. As linhas traçadas entre as cidades indicam quais percursos são operados pela empresa de transporte contratada.

Para essa instância, os melhores locais para instalar centros de distribuição são Amparo e Campinas. Para essa escolha, Limeira tem a maior distância de atendimento.

Escreva um programa centros que selecione as duas cidades em que devem ser instalados os novos centros e compute a maior distância de atendimento com esses dois centros.

Entrada

A primeira linha contém o número de cidades atendidas. Cada cidade é representada por uma linha com uma string sem espaços correspondendo ao nome e um número inteiro correspondendo à população. Em seguida há o número de percursos possíveis entre duas cidades. Cada percurso é representado por uma linha como o nome das cidades que conecta e a distância entre elas.

11
Amparo 73145
Atibaia 145378
Braganca 172346
Campinas 1223237
Capivari 56973
Holambra 15605
Limeira 310783
Piracicaba 410275
Socorro 41690
Sumare 289875
Tiete 42946
14
Amparo Holambra 42
Amparo Socorro 41
Braganca Amparo 45
Braganca Atibaia 25
Campinas Amparo 68
Campinas Atibaia 60
Campinas Braganca 65
Campinas Capivari 53
Campinas Sumare 31
Capivari Piracicaba 39
Capivari Tiete 28
Sumare Holambra 61
Sumare Limeira 52
Sumare Piracicaba 49

Saída

O par de cidades em que devem ser instalados centros de distribuição e a maior distância de atendimento para essa escolha. Em caso de empate, prefira o par de cidades que somadas têm maior população.

Centros de distribuicao: Amparo e Campinas
Distancia de atendimento: 83

Critérios

É obrigatório utilizar um grafo para representação do estado e as ligações entre as cidades.

← Anterior Voltar Próximo →