## Description

## Exercise 1 Minimum Spanning Trees

Write a C++ program in a file mst.cc that reads an adjacency list from the

standard input and outputs the minimum spanning tree (MST) and its cost

on the standard output. The input should start with a single line containing

the number of vertices.

Afterwards, the input should have one line for each

vertex in the graph and starts with a one letter vertex label in the range a–z.

Then it should list labels and weights of the all other vertices connected to

this vertex one after the other. Your output should start with a single line

containing the cost of the MST followed by lines each containing the vertex

labels of each edge in the MST.

All submissions have to follow the following input/output format exactly. The example below has four vertices a–d and four edges. a

is connected to b with an edge of weight 5, and to d with an edge of weight

1.

Example Input:

4

a b 5 d 1

b a 5 d 8

c d 15

d a 1 b 8 c 15

Example Output:

21

a b

a d

d c

1

## Exercise 2 Shortest Paths

Write a C++ program in a file named shortest.cc that reads an adjacency

list from the standard input and outputs the shortest paths from the first

vertex to all others and the path costs on the standard output. The input

should start with a single line containing the number of vertices. Afterwards,

the input should have one line for each vertex in the graph and it should

start with a one letter vertex label in the range a–z.

Than it should list

labels and weights of the all other vertices connected to this vertex one after

the other. Your output must have one line per target vertex that contains

the label of the target vertex and the cost of the shortest path.

All submissions have to follow the following input/output format exactly. The example below has four vertices a–d and four edges. a

is connected to b with an edge of weight 5, and to d with an edge of weight

1.

Example Input:

4

a b 5 d 1

b a 5 d 8

c d 15

d a 1 b 8 c 15

Example Output:

b 5

c 16

d 1

2