Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
30
1ºAlgorytmygrσfowe
Listing10120(cd0)
12
13
14
}
cin
gºEdgęU(b>ę);
>>
b
>>
ę;
//WykonajalgorytmDFSiwypiszwynik
15
gºDfs(s);
16
REP(Ü>SlZE(gºg))cout
<<
flWięrzcholękfl
<<
Ü
<<
fl.czaswęjscia=fl
17
<<
gºg[Ü]ºd
<<
fl9czaswyjscia=fl
<<
gºg[Ü]ºf
<<
18
fl9ojcięcwlęsięDFS=fl
<<
gºg[Ü]ºs
<<
ęndl;
19
return0;
20}
º
ZADANIE1KOMIWOJAŻERBAJTAZAR
Pochodzenie.
IXOlimpiidiInformityczni
Rozwiązanie.
kom0Cpp
KomiwojσżerBσjtσzσrciężkoprσcuje,podróżującpoBσjtocjiºWdσwnychczσsσchko-
miwojσżerowiesσmimogliwybierσćmiσstσ,którechcieliodwiedzić,ikolejność,wjσkiej
toczynili,jednσkteczσsyminęłyjużbezpowrotnieºZchwiląutworzeniσCentrσlnego
UrzędudsºKontroliKomiwojσżerówkσżdykomiwojσżerotrzymujezUrzędulistęmiσst,
któremożeodwiedzić,ikolejność,wjσkiejpowinientouczynićºJσktozσzwyczσjby-
wσzcentrσlnymiurzędσmi,nσrzuconσkolejnośćodwiedzσniσmiσstniemσzbytdużo
wspólnegozkolejnościąoptymσlnąºPrzedwyruszeniemwtrσsęBσjtσzσrchciσłbyprzy-
nσjmniejdowiedziećsię,ileczσsuzσjmiemuodwiedzeniewszystkichmiσstTobliczenie
tegojestTwoimzσdσniemº
MiσstσwBσjtocjisąponumerowσneod
1
do
n
ºNumer
1
mσstolicσBσjtocji,zniej
włσśnierozpoczynσpodróżBσjtσzσrºMiσstσpołączonesąsieciądrógdwukierunkowychº
Podróżmiędzydwomσmiσstσmibezpośredniopołączonymidrogązσwszezσjmuje
1
jed-
nostkęczσsuºZestolicymożnσdotrzećdowszystkichpozostσłychmiσstBσjtocjiºJednσk
siećdrógzostσłσzσprojektowσnσbσrdzooszczędnie,stąddroginigdynietworzącykliº
Zadanie
Nσpiszprogrσm,któryl
.
wczytσzestσndσrdowegowejściσopissiecidrógBσjtocjiorσzlistęmiσst,które
musiodwiedzićBσjtσzσr,
.
obliczysumσrycznyczσspodróżyBσjtσzσrσ,
.
wypiszewyniknσstσndσrdowewyjścieº
wejście
Wpierwszymwierszuwejściσzσpisσnσjestjednσliczbσcσłkowitσ
n
równσliczbiemiσst
wBσjtocji(
1<n<30000
)ºWkolejnych
n−1
wierszσchopisσnσjestsiećdrógT
