| Fişierul intrare/ieşire: | asfalt.in, asfalt.out | Sursă | Lot Sibiu 2011 |
| Autor | Andrei Parvu, Bogdan-Cristian Tataroiu, Cosmin Gheorghe, Mugurel Ionut Andreica | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Asfalt
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!
Date de intrare
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.
Date de ieşire
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.
Restricţii
- 1 ≤ N ≤ 500
- 1 ≤ M ≤ 5000
- 1 ≤ c ≤ 106
- 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
Exemplu
| asfalt.in | asfalt.out |
|---|---|
| 4 4 1 4 1 2 1 1 3 2 2 4 2 3 4 1 | 2 1 2 1 3 |
