Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Prepared by Ibrahim Mesecan.
Rruga me e shkurter
English
Nje "Minimum spanning tree" e nje grafi te padrejtuar G eshte nje peme
qe formohet duke lidhur brinjet e grafit qe permbajne koston me te vogel duke perfshire ne te
cdo kulm.
Pyetja:
Shkruani nje program qe gjen pemen me brinje me kosto me te vogla qe i permban te gjitha kulmet.
Note: Eshte e dhene qe grafi eshte i lidhur(nga cdo kulm mund te shkohet tek cdo kulm). Gjithashtu qyteti fillestar(kulmi i pare)
eshte qyteti i pare qe do jepet ne input.
Formati i inputit
Rreshti i pare permban nje numer te plote (V) i cili perfaqeson
numrin e kulmeve. Me pas, ne V rreshtat pasardhes,
do t'ju jepet emri i qytetit i ndjekur nga V numra te plote, te cilet jane distancat (d) nga ky qytet tek cdo qytet tjeter
ku 2 ≤ V ≤ 60. Distanca (d) do te jete nje numer i plote nga 1 tek 1000 dhe nje distance negative do te merret sikur ska rruge ndermjet ketyre dy qyteteve.
Formati i outputit
Nxirrni nje numer te plote, qe eshte kostoja totale e "Minnimum Spanning Tree".
Shembull
7
Tirana -1 2 4 1 -1 -1 -1
Elbasan 2 -1 -1 3 10 -1 -1
Vlora 4 -1 -1 2 -1 5 -1
Peshkopia 1 3 2 -1 2 8 4
Fier -1 10 -1 2 -1 -1 6
Durres -1 -1 5 8 -1 -1 1
Kavaja -1 -1 -1 4 6 1 -1
|
Pergjigja
12
|
Для отправки решений необходимо выполнить вход.
|