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

CAIXVIAJ - Caixeiro Viajante

Jean é um caixeiro viajante. Ele sempre está viajando entre uma cidade e outra. Quando ele chega em uma cidade, ele vende tudo que ele tem e compra coisas novas. Então, ele viaja para outra cidade, vende suas coisas e compra outras novas.

Neste problema, você deverá encontrar a quantidade total de dinheiro que Jean ganhará em uma jornada. Em uma jornada, ele pode ir para uma cidade mais de uma vez e ele deve terminar a jornada em alguma cidade da lista de cidades finais. Existe também uma cidade inicial para sua jornada e um número de viagens entre duas cidades que Jean deseja fazer durante a sua jornada.

Entrada

O arquivo de entrada contém vários conjuntos de entrada. A descrição de cada conjunto é dada a seguir:

Cada conjunto começa com quatro inteiros: C (2 ≤ C ≤ 100), o número de cidades, S (1 ≤ S ≤ 100), o identificador da cidade de início, E (1 ≤ E ≤ 100), o número de cidades nas quais a jornada pode terminar, e T (1 ≤ T ≤ 1000), o número de viagens entre duas cidades que Jean quer fazer.

Seguem C linhas com C inteiros não-negativos. O j-ésimo inteiro da i-ésima linha descreverá o lucro que Jean tem quando ele vai da cidade i para a cidade j. Como ele não quer fazer uma viagem para a cidade na qual ele já está, o i-ésimo inteiro da i-ésima linha sempre será 0. Note que ir da cidade i para a cidade j pode ocasionar um lucro diferente daquele de ir da cidade j para a cidade i.

Por fim, haverá uma linha com E inteiros, representando os identificadores das cidades nas quais Jean pode terminar a sua jornada.

A entrada é terminada por um conjunto onde C=S=E=T=0. Este conjunto não deve ser processado. Há uma linha em branco entre dois conjuntos de entrada.

Saída

Para cada conjunto de entrada produza uma linha de saída, o lucro total que Jean pode obter na jornada correspondente.

Exemplo

Entrada:
3 1 2 2
0 3 5
5 0 1
9 2 0
2 3

0 0 0 0

Saída:
7


Autor do Problema: João Paulo Fernandes Farias

Adicionado por:Wanderley Guimarăes
Data:2007-10-11
Tempo limite:0.156s
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 Seletiva para Maratona de Programacao UFRN - 2004

hide comments
2012-02-19 02:24:58 Renato Higor do Nascimento
Que triste, funfou beleza aqui mas no site sempre passa do tempo limite :/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.