== include(page="template/taskheader" task_id="asfalt") ==
Poveste şi cerinţă...
Băştinaşii din insula BuruBuru tocmai au descoperit asfaltul, aşa că şi-au unit cele $N$ sate (numerotate de la $1$ la $N$) prin $M$ drumuri bidirecţionale, fiecare de o lungime dată.
Văzând aceste progrese tehnologice, nişte colonişti au hotărât că vor să pună stăpânire pe insulă. Aceştia pleacă din satul cu indice $S$ (locul unde au debarcat) şi se indreaptă către capitala băştinaşilor, oraşul $D$, mergând pe ruta de lungime minimă (suma lungimilor drumurilor ce alcătuiesc ruta să fie minimă).
Băştinaşii doresc să mai amâne atacul coloniştilor, aşa că ar vrea să ştie care este numărul minim de drumuri cărora trebuie să li se mărească lungimea cu cel puţin o unitate astfel încat lungimea rutei de la oraşul $S$ la orasul $D$ să crească cu cel puţin o unitate. Deoarece băştinaşii încă nu au descoperit calculatorul, este de datoria voastră să îi ajutaţi!
h2. Date de intrare
Fişierul de intrare $asfalt.in$ ...
Pe prima linie a fişierului $asfalt.in$ se află patru numere $N$, $M$, $S$ şi $D$ cu semnificaţia de mai sus. Următoarele $M$ linii conţin câte trei numere $x$, $y$, $c$ fiecare, semnificând faptul că există un drum între oraşele $x$ şi $y$ de lungime $c$.
h2. Date de ieşire
În fişierul de ieşire $asfalt.out$ ...
Fişierul $asfalt.out$ va conţine pe prima linie numărul minim de drumuri a căror lungime trebuie mărită. Următoarele linii vor conţine fiecare câte două numere naturale, reprezentând indicii oraşelor ce descriu unul din drumurile ce trebuie mărite.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 500$
* $1 ≤ M ≤ 5000$
* $1 ≤ c ≤ 10^6^$
* $1 ≤ x, y ≤ N$
* orice soluţie ce are un număr minim de drumuri este acceptată
* nu vor exista mai multe drumuri între două oraşe
h2. Exemplu
table(example). |_. asfalt.in |_. asfalt.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|4 4 1 4
1 2 1
1 3 2
2 4 2
3 4 1
|2
1 2
1 3
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="asfalt") ==
