Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

REUNIAO2 - Reunião

Todos os anos, a SBC (Sociedade Brasileira de Caminhoneiros) reúne seus membros em alguma cidade para discutir sobre a profissão. Nessas reuniões são discutidos os problemas da categoria e são apresentadas sugestões sobre como melhorar as condições de trabalho.

O grande problema desse tipo de encontro é que os membros estão espalhados pelo país, uma vez que a profissão exige que eles viajem para diversos lugares todos os dias. Por isso, a escolha da cidade onde será feita a reunião sempre é feita de modo que não prejudique demais nenhum dos caminhoneiros. O critério para tal é que a maior das distâncias percorridas pelos caminhoneiros para chegar ao local da reunião deve ser a menor possível. Ou seja, a distância percorrida pelo caminhoneiro que vai percorrer a maior distância entre todos os caminhoneiros para chegar à reunião deve ser a menor possível.

Tarefa

Dadas as cidades onde se encontram os caminhoneiros e a descrição das estradas que interligam essas cidades, escreva um programa que determina qual será a menor distância máxima percorrida por um caminhoneiro para chegar até o local da reunião. Os caminhoneiros conhecem bem as estradas, e portando sempre fazem o menor caminho possível até a cidade da reunião. Sempre existe um caminho ligando quaisquer duas cidades.

Entrada

A primeira linha da entrada possui dois números inteiros N (2 ≤ N ≤ 100) e M (N - 1 ≤ M ≤ 10000), que representam, respectivamente, o número de cidades e o número de estradas que as interligam. As cidades são identificadas por números inteiros entre 0 e N - 1. As próximas M linhas da entrada possuem, cada uma, a descrição de uma estrada. Cada descrição de entrada é composta por três números inteiros: U, V e W, onde U e V representam cidades (0 ≤ U ≤ N - 1 e 0 ≤ V ≤ N - 1) e W representa o comprimento da estrada que une essas duas cidades (todas as estradas são mão dupla, 1 ≤ W ≤ 100). É sempre possível viajar entre qualquer duas cidades com as estradas existentes, mas pode haver mais de uma estrada ligando o mesmo par de cidades .

Saída

Seu programa deve imprimir uma única linha contendo um número inteiro, a distância máxima percorrida por um caminhoneiro para ir até a reunião, obedecidas as restrições estabelecidas (ou seja, essa distância máxima deve ser a menor possível).

Exemplo

Entrada
4 4
0 1 2
0 2 4
1 3 1
2 3 5

Saída
4

Entrada
4 5
0 1 2
0 2 4
1 3 1
2 3 5
3 2 2

Saída
3

Entrada
7 12
0 1 22
0 2 30
0 5 35
1 5 11
1 6 30
1 2 25
2 3 15
2 6 10
3 4 15
3 5 10
4 5 20
5 6 33

Saída
30


Adicionado por:Wanderley Guimarăes
Data:2011-04-28
Tempo limite:0.207s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:OBI 2010 - fase 1 nível 2

hide comments
2016-04-18 00:36:39 Elsio [UFABC]
Similares:
http://br.spoj.com/problems/SUPERMER/
http://br.spoj.com/problems/DENGUE/
2016-04-18 00:31:04 Elsio [UFABC]


Last edit: 2016-09-02 01:02:56
2016-04-03 02:35:22 Elsio [UFABC]
Busca do centroide do grafo por Floyd Warshall. Pega o menor valor entre os maiores valores de cada linha. Também dá pra fazer por desfolhamento, mas não sei como seria com grafos valorados.
2012-09-27 22:49:43 Tiago Reis [UFSCar]
O problema pede que VOCĘ decida a cidade onde vai ser a reuniăo. O Sohakes está certo e, bem... eu diria que é pra resolver do jeito óbvio, mesmo =p
2012-05-18 19:34:03 Sohakes
Se entendi bem, tem que considerar a maior distância entre todas as cidades de onde sai caminhăo e todas as cidades que podem ser reuniăo. Ou seja, achar um par de vértices com maior menor caminho. Além do jeito óbvio, năo sei como resolve isso :(.
2012-01-25 01:00:46 Mr. Anderson [UERN]
Realmente năo ficou claro. Năo deveria dizer onde vai ser a reuniăo?
2012-01-09 18:00:53 Luiz Augusto de M. Morais
Qual eh a cidade da reuniao?

Last edit: 2012-01-09 18:01:32
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.