HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > "Informatics Stars" Online Contests - 2011-2014 > problem:


2014-04-50. 50703 - The Shortest Path

"Informatics Stars" Online Contests - 2011-2014

Start: Oct.20.2012 at 10:00:00 AM
Finish: Oct.20.2012 at 03:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 2013-01-10. 50584 - Total invoice ...
• 2013-01-30. 50599 - Sum of Squar...
• 2013-03-20. 50578 - Mersenne prime
• 2013-03-30. 50360 - National Elections
• 2013-03-40. 50705 - Student Clubs
• 2014-04-10. 50547 - Close Pair
• 2014-04-30. 50560 - Max Distance
• 2014-04-50. 50569 - 12th Grade Ele...
• 2014-04-50. 50703 - The Short...

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Prepared by Ibrahim Mesecan.

The shortest path

Shqip

A minimum spanning tree of an undirected graph G is a tree formed from graph edges that connects all the vertices of G at lowest total cost.

Question:
Write a program that finds the shortest path that spans all the vertices.
Note: It's provided that the graph is connected. And, assume that the source city (starting vertex) is the first city given in the text.

Input specification
The first line contains an integer (V) which represents the number of vertices. Then, in the following V lines, you will be given a city name that is followed by V numbers which are the distances (d) from the source city to other cities where 2 ≤ V ≤ 60. Assume that d is an integer distance between 1 and 1000 and a negative value means that there is no edge between the given cities.

Output specification
Show one integer, the cost of minimum spanning tree.

Sample Input I   
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
Sample Output I   
12


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

www.contester.ru