Problem A. Fast Dijkstra
Statement
You are to write a program that receives a weighted directed graph and finds
all distances from fixed vertex S to all other vertices. Distance from S to
some vertex W is the minimal length of path going from S to W. Length of path
is the sum of weights of its arcs.
Input file format
Input file contains two integers N, M and S.
Vertices are numbered with integer numbers from 1 to N. S is the number of
source vertex. M is the number of arcs. Each of next M lines contain three
integers — numbers of starting and ending vertices of some arc and its weight
respectively. All weights are positive. There is at most one arc connecting
two vertices in every direction.
Output file format
Output file must contain N numbers. Each I-th number is the distance from
vertex S to vertex I. If some vertices are not reachable from S, corresponding
numbers must be −1.
Constraints
1 ≤ N, M ≤ 100000
All weights are less or equal 1000.
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
5 3 1
1 2 5
1 3 7
3 4 10
|
0 5 7 17 -1
|
Problem B. Shortest Spanning Tree
Statement
You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.
Input file format
Input file contains two integers N, M.
Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three
integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are
positive. There is at most one edge connecting two vertices.
Output file format
Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree,
output file must contain −1.
Constraints
1 ≤ N ≤ 1000
All weights are less or equal 1000.
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
3 3
1 2 10
2 3 10
3 1 10
|
20
|
Problem C. SST for sparse graph
Statement
You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.
Input file format
Input file contains two integers N, M.
Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three
integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are
positive. There is at most one edge connecting two vertices.
Output file format
Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree,
output file must contain −1.
Constraints
1 ≤ N, M ≤ 100000
All weights are less or equal 1000.
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
3 3
1 2 10
2 3 10
3 1 10
|
20
|
