ultima problemă
grupă: micăsursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
lanturi
Timp maxim de execuţie/test:
0.1
secunde
Memorie totala disponibilă/stivă:
16
MB/1 MB
Fie un graf neorientat cu n noduri şi m muchii; fiecare muchie din graf are asociat un cost.
Cerinţă
Scrieţi un program care determină numărul de lanţuri de cost minim ce leagă nodul x de y .
Date de intrare
Fişierul de intrare lanturi.in conţine pe prima linie numerele naturale n m x y despărţite prin câte un spaţiu. Următoarele m linii conţin triplete de numere naturale de forma i j c , despărţite prin câte un spaţiu, având semnificaţia că există muchie între nodul i şi j de cost c .
Date de ieşire
Fişierul de ieşire lanturi.out va conţine o singură linie pe care va fi scris numărul de lanţuri de cost minim ce leagă nodul x de y .
Restricţii
1 <= n <= 1 000 1 <= m <= 1 500 1 <= c <= 100 0 <= numărul de lanţuri determinat <= 264 -1 Costul unui lanţ este egal cu suma costurilor muchiilor ce constituie lanţul .
Exemple
lanturi.in lanturi.out Explicatie
5 8 1 5
5 Costul minim este 4 şi se obţine pe lanţurile: 1 4 5
Articole recomandate
Probleme recomandate
De la .campion 2009 : efort , muzeu , bal , seti , basm , dansatori , smith , timer , secvsir , vot , cetati , reziduu , biliard , prefix1 , accesibil , dp , jocv , placa , palc , prod3 , predecesor , standard , cantor , nkbiti , nori , triti , kperms , sotron1 , impozit , tablite , fazan , secvpar , tom , joker , matriosca , asociativ , lego , medalii , permutari , cfr , treegame , scanduri , site , fotbal , links , kbiti , segm , album , iepurasi , jucarii , m4 , bradut , trmv , colorare , greutati , concat , graphgame , ic , echilibru , brazi , mat , cubinvers , mobil , distsir , parbit De acelaşi autor : compus , taste , arce , balbe , drept , scor , sume3 , spair , bitslang , police , tree , reteta2 , farfurii , caramele , apm , maraton , masina1 , bomboane , soldati1 , concurs1 , puncte , pipe , camion , imax , litoral , dreptc , bal , prefix1 , tablite , loto , bila , popic , activ , game1 , pitag , secv9 , divk , taler , bdotcom , oak , ozn1 , optim , puncte5 , swap , tetris3 , monede2 , ssk Despre coada : balanta , inginer , camp , rebus , harta , insule , volei , lbd , magic3 , axa , cadere , reinvent , ocean14 , iepuras2 , sah , balls , cd , toys , radio , caini , subperm , castel , excursia , casute , soricel2 , masina2 , salvare , paianjen , suma2 , garaj , alee , lanterna , rj , caraibe , taxe1 , sotron1 , tom , k1 , dreptunghiuri , sokoban , ny , oldest , drumuri1 , alpinist , tsunami , robot3 , joc19 , valet , oras1 , gheizere , zone , taxa , abq , cartite , joc21 , traseu3 , panda , expand Despre graf : gropi , tgv , matrice2 , miniasm , picnic , mere , circuit , soldati , arce , conflicte , desen , robot , furtuna , net , cuvinte , excursie , cadere , pioni , reinvent , kreg , flood , croco , johnie , matrice , arthur , kimberley , ro , sol , caravane , bete , honest , police , pcod , zmeu , auto2 , grazing , datorii , trafic , sponsori , monede1 , apm , bile1 , caini , masina1 , bomboane , turn1 , shgraf , paintball , program1 , tgraf , kgb , algola , felinar , joc6 , tric , homeless , promo , turism , casute , joc10 , prieteni1 , traseu , zapezi , litoral , lover , trip , garaj , ziduri , tv , pact , echipe1 , vitale , spion , trasee , bcolor , scara2 , lant , ab3 , soc , team , gard , rsp , graf , mexc , dep , albinuta1 , atac2 , cabane , drumuri , tj , grade , jungla , lanterna , magic5 , coment , urgenta , fazan , cfr , site , traseu1 , trmv , graphgame , minuni , telefon , ubergraf , carray , pestera , chei , arbgraf , war , fluviu , drumuri1 , entries , ubuntzei , pack , fotbal1 , pamant , dag , razboi , benzina2 , wg , neconex , asfalt1 , kubus2 , module , progresii , dfs , prieteni3 , megascoala , grafxy , dineu , vot1 , biperm , drumuri2 , nrgraf , cristal , cartite , copaci3 , dragoni , nuclee Despre drum minim : miniasm , robot , furtuna , excursie , arthur , bete , zmeu , trafic , masina1 , bomboane , traseu , litoral , lover , trip , scara2 , team , gard , pitici1 , base3 , coach , trmv , pestera , fluviu , ubuntzei , razboi , benzina2 , kubus2 , megascoala , dragoni