ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > "Informatics Stars" Online Contests - 2011-2014 > задача:


2014-04-50. 50703 - Rruga me e shkurter

"Informatics Stars" Online Contests - 2011-2014

Старт: 20.окт.2012 в 10:00:00
Финиш: 20.окт.2012 в 15:00:00
Турнир завершён!
• Турнирная таблица

Гость
• Вопросы к жюри (1)

Задачи турнира

• 2013-01-10. 50584 - Pagesa totale
• 2013-01-30. 50599 - Shuma e katro...
• 2013-03-20. 50578 - Numrat Prim M...
• 2013-03-30. 50360 - National Elections
• 2013-03-40. 50705 - Klubet e studen...
• 2014-04-10. Cifti me i afert
• 2014-04-30. 50560 - Distanca maks...
• 2014-04-50. 50569 - Lendet me zgj...
• 2014-04-50. 50703 - Rruga me e...

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 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


Для отправки решений необходимо выполнить вход.

www.contester.ru