Fişierul intrare/ieşire:asfalt.in, asfalt.outSursăLot Sibiu 2011
AutorAndrei Parvu, Bogdan-Cristian Tataroiu, Cosmin Gheorghe, Mugurel Ionut AndreicaAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inasfalt.out
4 4 1 4
1 2 1
1 3 2
2 4 2
3 4 1
2
1 2
1 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content