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

DESVIO - Desvio de rota

O sistema rodoviário de um país interliga todas as suas N cidades de modo que, a partir de uma cidade qualquer, é possível chegar a cada uma das outras cidades trafegando pelas estradas existentes. Cada estrada liga duas cidades distintas, tem mão dupla e um único posto de pedágio (o pedágio é pago nos dois sentidos de tráfego). As estradas não se intersectam a não ser nas cidades. Nenhum par de cidades é interligado por duas ou mais estradas.

A Transportadora Dias oferece um serviço de transporte de encomendas entre as cidades. Cada encomenda deve ser levada de uma cidade A para uma outra cidade B. A direção da Transportadora Dias define, para cada encomenda, uma rota de serviço, composta por C cidades e C−1 estradas: a primeira cidade da rota de serviço é a origem da encomenda, a última o destino da encomenda. A rota de serviço não passa duas vezes pela mesma cidade, e o veículo escolhido para fazer o transporte de uma encomenda pode trafegar apenas pela rota de serviço definida.

Certo dia, no entanto, o veículo que executava uma entrega quebrou e precisou ser levado para conserto em uma cidade que não está entre as cidades de sua rota de serviço. A direção da Transportadora Dias quer saber qual é o menor custo total, em termos de pedágio, para que o veículo entregue a encomenda na cidade destino, a partir da cidade em que foi consertado, mas com uma restrição adicional: se em algum momento o veículo passar por uma das cidades que compõem a sua rota de serviço, ele deve voltar a obedecer a rota de serviço.

Entrada

A entrada contém vários casos de teste. A primeira linha de um caso de teste contém quatro inteiros N, M, C e K (4 ≤ N ≤ 250, 3 ≤ MN×(N−1)/2, 2 ≤ CN−1 e CKN−1), representando, respectivamente, o número de cidades do país, o número de estradas, o número de cidades na rota de serviço e a cidade em que o veículo foi consertado. As cidades são identificadas por inteiros de 0 a N−1. A rota de serviço é 0, 1, ... , C−1, ou seja, a origem é 0, de 0 passa para 1, de 1 para 2 e assim por diante, até o destino C−1.

As M linhas seguintes descrevem o sistema rodoviário do país. Cada uma dessas linhas descreve uma estrada e contém três inteiros U, V e P (0 ≤ U, VN−1, UV, 0 ≤ P ≤ 250), indicando que há uma estrada interligando as cidades U e V com custo de pedágio P. O último caso de teste é seguido por uma linha contendo quatro zeros separados por espaço em branco.

Saída

Para cada caso de teste, o seu programa deve imprimir uma única linha, contendo um único inteiro T, o custo total mínimo necessário, em termos de pedágio, para que o veículo chegue ao destino.

Exemplo

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

Saída:
10
6
6


Adicionado por:Wanderley Guimarăes
Data:2011-02-12
Tempo limite:1s
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:Primeira fase da Maratona de Programação - 2010

hide comments
2020-02-20 14:51:42
Já estou há dois dias nesse problema e até agora não consegui. Estou fazendo uma modificação no dijkstra, colocando uma condicional antes da verificação dos vizinhos. Se o vértice "u" pertence a rota original e o vértice "u+1" não é o destino , adiciono "u+1" na lista de prioridade. Alguém pode me ajudar?
2015-06-29 14:54:46 Elsio [UFABC]
Finalmente consegui! Acho que a dica mais importante é: existe pedágio com custo zero.
2015-06-28 02:03:19 Elsio [UFABC]
Apesar do problema dizer que as ruas tem mão dupla, trata-se de um caso de grafo ponderado orientado.
2015-06-28 01:47:12 Elsio [UFABC]
Ah tah. já entendi. ele não pode fazer o caminho 3, 0, 2 com 2 de pedágio por causa da restrição de ter que andar na sequência. E o destino é C-1, no caso, 2. Se seguirmos a restrição o pedágio será 21, mas tem um caminho direto por 10.

Last edit: 2015-06-28 01:59:10
2014-06-20 20:39:32 Wilson [UNESP]
Năo Andrei, tem um caminho de 3 para 2 com pedágio 10...
2013-09-17 00:40:36 Andrei [FATEC-BS]
Acredito que a primeira saída está errada. A saída correta seria 21.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.