Fişierul intrare/ieşire:traveling.in, traveling.outSursăShumen 2016 Juniori
AutorAdăugată despatarelSpatarel Dan-Constantin spatarel
Timp execuţie pe test2.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Traveling

Ivan Cel Rapid trebuie să plătească din fonduri proprii călătoria spre locul unde urmează să se desfăşoare următorul concurs de programare. El dispune doar de S euro. Din acest motiv, el a verificat cu mare grijă programul mijloacelor de transport în comun şi bineînţeles preţurile. O să notăm cu 1 locul de plecare, cu N locul unde urmează să se desfaşoare concursul şi cu 2, 3, ... N - 1 celelalte oraşe prin care ar putea să treacă. Ivan a găsit M curse de forma: cursa între oraşele v şi w durează t ore şi are tariful de e Euro în ambele sensuri. Pot exista mai multe curse între oraşele v şi w. Acestea pot varia atât ca durată cât şi ca tarif.

Să se scrie un program care găseşte o călătorie de la oraşul 1 la oraşul N la un tarif mai mic sau egal cu S. Dacă există mai multe variante de a călători, programul va afisa varianta în care timpul petrecut pe drum este minim.

Date de intrare

Fişierul de intrare traveling.in conţine pe prima linie numerele întregi pozitive S, N şi M. Fiecare din următoarele M linii conţine 4 numere întregi: v, w, t şi e (descriind o cursă).

Date de ieşire

În fişierul de ieşire traveling.out se va găsi durata călătoriei. Dacă nu se găseşte nicio variantă de călătorie la un tarif mai mic sau egal cu S, programul o să afişeze -1.

Restricţii

  • S ≤ 2 000
  • N ≤ 3 000
  • M ≤ 5 000
  • 1 ≤ vN
  • 1 ≤ wN
  • 1 ≤ t ≤ 100
  • 1 ≤ e ≤ 100

Exemplu

traveling.intraveling.out
7 4 6
1 2 2 5
1 3 2 2
1 4 7 3
2 3 1 2
2 4 2 3
3 4 5 2
5
4 4 6
1 2 2 5
1 3 2 2
1 4 7 5
2 3 1 2
2 4 2 3
3 4 5 3
-1
Trebuie sa te autentifici pentru a trimite solutii. Click aici