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

Разделы > Задачи на графах > задача:


50703 - Rruga me e shkurter

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

Задачи раздела

• 50857 - Nine-Stones Game
• 50929 - Present from your uncles
• 51076 - Key person
• 51080 - Deepest Point
• 51079 - Key person - 2
• 50464 - From Tirana to Durres
• 50691 - Задача коммивояжёра
• 50701 - Cell Removal
• 50703 - Rruga me e shkurter
• 50704 - Te lidhura?
• 50705 - Klubet e studenteve

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

Если у вас есть предложения или пожелания по работе 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