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.|

ENGARRAF - Engarrafamento

Autor: Tiago Mota

Cansado dos constantes engarrafamentos que enfrenta todo dia para chegar ao trabalho com seu carro, Antônio resolveu reclamar com a secretaria responsável pelo controle de tráfego de sua cidade. Porém, ao entrar em contato com tal órgão, descobriu que este disponibiliza mapas das ruas da cidade, com o tempo que um carro costuma gastar para atravessar cada uma das ruas durante o período de engarrafamento. Com estas informações, ele pôde descobrir o caminho mais rápido de sua casa até seu local de trabalho, podendo, assim, acordar mais tarde e dormir um pouco mais todo dia.

Empreendedor nato, Antônio percebeu que as informações colhidas junto à secretaria poderiam ser úteis para ele de outra forma. Decidiu, então, criar um programa de computador para ajudar seus colegas de trabalho que enfrentam o mesmo problema, indicando os caminhos mais rápidos entre pontos da cidade selecionados pelo usuário. Naturalmente, esta ajuda não será gratuita, já que Antônio pretende cobrar pelo uso do programa.

Antônio, porém, não tem tempo livre suficiente para programar. Como você é um estagiário da empresa que está logo abaixo de Antônio, ele pede que você escreva um programa que, dado um mapa com as ruas e o tempo necessário para atravessar cada uma, calcule o tempo mínimo para se ir de um determinado local de origem a um determinado local de destino.

Entrada

A entrada é composta de vários casos de teste. Cada caso de teste é iniciado com uma linha contendo dois números inteiros, n e m (1 <= n <= 100, 0 <= m <= 10000), representando, respectivamente, o número de locais da cidade (identificados por inteiros de 1 a n) e o número de ruas a serem considerados.

A seguir, há m linhas, cada uma contendo três inteiros, i, j e t (1 <= i, j <= n, i ≠ j, 1 <= t <= 1000), indicando que há uma rua de mão única ligando os locais i e j, nesta ordem, e cujo tempo de travessia é t. Para cada par de locais i e j, haverá no máximo uma rua ligando i a j e no máximo uma rua ligando j a i.

Finalmente, a última linha do caso de teste contém dois inteiros, s e d (1 <= s, d <= n), respectivamente, os locais inicial e final para os quais devemos calcular o tempo mínimo de trajeto.

A entrada termina quando n = m = 0.

Saída

Para cada caso de teste, seu programa deve imprimir uma linha com um único inteiro, representando o tempo mínimo necessário para se deslocar do local s ao local d. Se não for possível alcançar o local d a partir do local s, imprima -1 como resposta.

Exemplo

Entrada:
3 3
1 2 2
1 3 7
2 3 3
1 3
3 3
1 2 3
1 3 7
2 3 5
1 3
3 2
1 2 2
2 1 3
1 3
4 6
1 2 5
1 3 3
2 4 3
3 2 2
4 1 4
4 3 9
2 3
0 0

Saída:
5
7
-1
10

Adicionado por:Wanderley Guimarăes
Data:2008-07-08
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Segunda prova de TEP - 2008/1 - UFRJ

hide comments
2019-08-25 03:06:01
"A entrada termina quando n = m = 0.", parece que não, é quando qualquer um dos dois é 0, não quando ambos são 0.
2017-02-21 15:15:26 Kleber Vianna [FATEC/SP]
Não consigo de jeito nenhum fazer passar meu código em python. Estoura o tempo sempre! Alguém dá alguma ideia? Notei que só tem uma solução aceita em python. Como será que ele fez isso?!
Consegui fazer passar a mesma solução em C, mas uma dica se estiver utilizando Floydd-Warshall: ao inicializar a matriz-grafo a cada ciclo, a diagonal principal tem que se zerada.
2013-06-28 19:12:49 Marcelo Anselmo Gomes
limite ta errado mermo!!
2013-03-06 14:30:12 Lucas Leite [UFES]
Alguém sabe quais săo os limites corretos para essa questăo?
2012-10-14 01:49:49 Cristhian [UTFPR]
Eu levei mil WA graças ao teste onde s é igual a d ŹŹ
2012-07-06 14:11:06 Wesley Lencione de Oliveira[FATEC-Sorocaba]
Bom, o limite está incorreto, deixei como 10001 meu padrăo do grafo e năo passou, alterei pra 99999 e passou ;)
2011-10-10 17:52:47 Gabriel Luís Mello Dalalio [ITA]
Parece que tem caso de teste com n > 100, melhor assumir que n<=110 que passa
2011-02-05 22:24:45 Raul Dario Cabrera Tapia [POLI-USP]
Tomem cuidado com os limites!: (1 <= n <= 100, 0 <= m <= 10000); (1 <= i, j <= n, i ≠ j, 1 <= t <= 1000)

Last edit: 2011-02-05 22:26:22
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.