Diferențe pentru problema/traveling între reviziile #46 si #1

Traveling

traveling

== include(page="template/taskheader" task_id="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.

Poveste și cerință...

h2. 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ă).

Fișierul de intrare $traveling.in$ ...

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

În fișierul de ieșire $traveling.out$ ...

h2. Restricții

* $_S_ ≤ 2 000$
* $_N_ ≤ 3 000$
* $_M_ ≤ 5 000$
* $1 ≤ _v_ ≤ _N_$
* $1 ≤ _w_ ≤ _N_$
* $1 ≤ _t_ ≤ 100$
* $1 ≤ _e_ ≤ 100$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example).
|_. traveling.in |_. traveling.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

| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.

|

h3. Explicație
 
...
 

== include(page="template/taskfooter" task_id="traveling") ==