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
|
Для отправки решений необходимо выполнить вход.
|