28a Olimpíada Brasileira de Informática
Viagem
Você está viajando pelo arquipélago de Kiri, que é composto por um grande número de ilhas. Não há pontes entre as ilhas, de modo que a única maneira de viajar entre as ilhas é por navio. Há várias rotas de navios disponíveis. Cada rota conecta duas ilhas distintas A e B e pode ser usada nas duas direções (de A para B ou de B para A). Cada rota tem um certo tempo de percurso (o mesmo nas duas direções) e um custo (o mesmo nas duas direções). No momento você quer ir da ilha X para outra ilha Y, mas quer gastar no máximo um certo valor com a viagem. Você também está com pressa e gostaria de chegar o mais rapidamente possível ao seu destino. Dados a lista das rotas disponíveis, com seus custos e tempos de percurso, escreva um programa para determinar se é possível chegar ao destino gastando no máximo o valor previsto para a viagem, e nesse caso qual o menor tempo para chegar ao destino. Note que pode não ser possível chegar ao destino, seja porque não há rota disponível ou porque o valor alocado para a viagem não é suficiente. Por exemplo, considere o caso mostrado na figura abaixo, em que você está na ilha 1 e quer ir para a ilha 4:
- Se o valor previsto é 10, a resposta é 5 e o caminho ótimo é 1 → 2 → 4. Note que este caminho custa 4 + 6 = 10 e demora tempo 4 + 1 = 5.
- Se o valor previsto é 7, a resposta é 7 e o caminho ótimo é 1 → 2 → 3 → 4, que custa 4 + 2 + 1 = 7 e demora tempo 4 + 2 + 1 = 7.
- Se o valor previsto é 3, a resposta é 8 e o caminho ótimo é 1 -> 3 -> 4, usando a aresta entre 1 e 3 que demora tempo 7 e tem custo 2. Note que este caminho custa 2 + 1 = 3 e demora tempo 7 + 1 = 8.
- Se o valor previsto é 2, a resposta é 9 e o caminho ótimo é 1 -> 3 -> 4, usando a aresta entre 1 e 3 que demora tempo 8 e tem custo 1, note que este caminho custa 1 + 1 = 2 e demora tempo 8 + 1 = 9.
- Se o valor previsto é 1, não existe caminho que satisfaça as restrições, por isso a resposta é -1.
Entrada
A primeira linha da entrada contém três inteiros V, N e M, respectivamente o valor disponível para a viagem, o número de ilhas e o número de rotas. As ilhas são identificadas por inteiros de 1 a N. Cada uma das M linhas seguintes descreve uma rota e contém quatro inteiros Ai, Bi, Ti e Pi, onde Ai e Bi representam ilhas, Ti o tempo de percurso e Pi o custo de uma passagem para essa rota. A última linha da entrada contém dois inteiros X e Y, o início e o destino da sua viagem.Saída
Seu programa deve produzir uma única linha na saída, que deve conter um único inteiro, o menor tempo necessário para chegar ao destino, ou o valor -1 caso não seja possível chegar ao destino.Restrições
- 2 ≤ N ≤ 10 000
- 1 ≤ M ≤ 2 000
- 1 ≤ V ≤ 200
- 1 ≤ Ai, Bi ≤ N, Ai &neq; Bi, para 1 ≤ i ≤ M.
- Pode haver mais de uma rota entre o mesmo par de ilhas.
- 1 ≤ Ti ≤ 100 000, para 1 ≤ i ≤ M.
- 0 ≤ Pi ≤ 200, para 1 ≤ i ≤ M.
- 1 ≤ X,Y ≤ N
Informações sobre a pontuação
- Para um conjunto de casos de testes valendo 20 pontos, N ≤ 200 e Pi = 0 para 1 ≤ i ≤ M.
- Para um conjunto de casos de testes valendo outros 10 pontos, N ≤ 10 000 e Pi = 0 para 1 ≤ i ≤ M.
- Para um conjunto de casos de testes valendo outros 30 pontos, N ≤ 100 e V ≤ 10.
- Para um conjunto de casos de testes valendo outros 40 pontos, nenhuma restrição adicional.
Exemplos
Entrada
10 4 7 1 2 4 4 1 3 7 2 3 1 8 1 3 2 2 2 4 2 1 6 3 4 1 1 1 4 6 12 1 4 |
Saída
5 |
Entrada
3 3 3 1 2 5 2 3 2 8 2 1 3 1 4 1 3 |
Saída
-1 |