28a Olimpíada Brasileira de Informática
Submeta sua solução

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:
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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
	

 

PJ P1 P2 PS
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação