Exercicio da OBI 2008

[Korosi 0]

Errei no titulo mas tudo bem...hehe

 

Mal cheguei no forum (por sinal muito bom) e já venho com um daqueles...HauhUAhUAa

 

É o seguinte, sabado agora teve a OBI 2008, e me enfiei lá para ver em q nivel estou...e esse me pegou de jeito, entendi a lógica mais ou menos...ai vai o exercicio "resumido"...hahaha

 

Uma empresa decidiu posicionar uma cozinha em suas instalações. Analisando a planta do prédio é possível criar um diagrama contendo todas as salas, todos os corredores que as ligam e os seus respectivos comprimentos, em metros. A cozinha deve ser posicionada em uma das salas de tal forma que a distancia entre a cozinha e a sala mais distante da cozinha seja a menos possível.

Obviamente, a empresa deseja utilizar esse fato para anunciar que “nenhum de seus funcionários está a mais de X metros da uma cozinha”. Eles contrataram o seu escritório de arquitetura para posicionar a cozinha na sala que minimiza X e você, como programador, deve escrever um programa que informa qual será essa distancia.

 

ENTRADA

A entrada contem um único conjunto de testes. A primeira linha da entrada contem dois inteiros, S e C, (1<=S<=250, 1<=C<=50000) indicando, respectivamente, o numero de salas e o numero de corredores. As C linhas seguintes contem, cada uma, três inteiros, A, B e D (1<=A<=N, 1<=B<=N, 1<=D<=100, A!=B ) indicando que existe um corredor de D metros ligando as salas A e B. Cada corredor é informado uma única vez na entrada.

SAIDA

Seu programa deve imprimir, na saída padrão, uma única linha, contendo um inteiro indicando a distancia entre a cozinha e a sala mais distante, considerando que a cozinha foi posicionada na sala onde essa distancia é mínima.

 

EXEMPLO DE ENTRADA............................................EXEMPLO DE SAIDA

...........4 6 .........................................................................2

...........1 2 1

...........2 3 1

...........2 4 2

...........3 4 1

...........1 4 1

...........3 1 4

 

EXEMPLO DE ENTRADA............................................EXEMPLO DE SAIDA

...........4 4 .........................................................................10

...........1 2 10

...........2 3 1

...........3 4 4

...........2 4 3

 

EXEMPLO DE ENTRADA............................................EXEMPLO DE SAIDA

...........5 6.........................................................................11

...........1 2 10

...........2 3 10

...........2 4 11

...........2 5 11

...........3 4 10

...........4 5 10

 

Pois bem...pelo q entendi, seguindo o primeiro exemplo:

A cozinha deve ficar ou em 2 ou em 4, tendo 2m como maior distancia até uma sala...pois se ficar em 3 ou 1, a maior distancia seria de 4m...

 

Mas e dai?? Nao consegui bolar um algoritmo...

Qualquer ajuda é bem vinda...desculpe pelo tamanho do post http://forum.imasters.com.br/public/style_emoticons/default/blush.gif

[Pantoja 5]

teria como arrumar isso em imagem ou PDF?

 

 

abração

[Korosi 0]

teria como arrumar isso em imagem ou PDF?

 

 

abração

Nao tem...só se eu tirar foto da prova...hahaha

Mas nao fica muito legivel

 

Abraço

[Martin Fabichak 0]

problema de grafos...

 

tente dar uma estudada em algumas estruturas de dados básicas, e esse problema sái!

[Korosi 0]

Humm...valeu

Mas mesmo só sendo permitido resolver usando C/C++?

 

Saberia algum site ou livro para me indicar?