Submeter | Todas submissőes | Melhores | Voltar |
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
Adicionado por: | Wanderley Guimarăes |
Data: | 2007-10-11 |
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 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 :/ |