Minimum Spanning Tree with Optimal A-B Connection
Let G=(V, E) be an undirected graph and let A, B be its two vertices. We say that a spanning tree T of graph G connects A and B optimally if and only if the edge distance between A and B in T equals the edge distance between A and B in G.The edge distance between A and B is equal to the least possible number of edges on any path from A to B.
Figure 1. a) A weighted undirected graph consisting of 10 vertices and 13 edges. The weigths are depicted by the red numbers. The edge distance between vertices 5 and 9 is 4. The blue edges form a spanning tree which connects vertices 5 and 9 optimally and whose cost is minimal among all such spanning trees. b) A graph with 9 vertices and 12 edges. The blue edges again represent a spanning tree which connects vertices 3 and 6 optimally and is of a minimum cost. |
The task
Given a weighted undirected graph and two its vertices A, B, find a spanning tree which connects A and B optimally and whose cost is minimal possible.
Input
The first input line contains four integers N, M, A and B separated by space. N is the number of vertices,
M is the number of edges, A and B are identifiers of two vertices (all the vertices are numbered from 1 to N).
Next, there are M lines with triples of integers V1, V2, W separated by space,
representing an undirected edge of weight W between vertices V1 and V2.
The edges are listed in random order.
It holds N ≤ 210000, M ≤ 250000. Each weight is a positive integer not greater than 200.
Output
The output contains one line with two integers L and C separated by space where L is the edge distance between A and B, and C is the minimum cost of a spanning tree that connects vertices A and B optimally.
Example 1Input10 13 5 9 1 2 1 1 3 2 2 4 2 3 5 1 3 7 2 4 7 4 4 9 2 5 6 2 6 7 4 7 8 1 8 9 3 6 10 3 10 8 2Output 4 16 |
Example 2Input9 12 3 6 3 1 4 1 2 4 2 6 4 3 4 3 4 5 3 5 6 3 3 7 1 7 4 1 4 8 1 8 5 1 5 9 1 9 6 1Output 3 17 |
Example 3Input8 16 7 3 7 8 1 8 1 3 1 2 1 2 3 2 3 4 1 4 5 3 5 6 1 6 7 2 7 1 1 1 3 4 3 5 2 5 7 3 6 8 1 8 2 3 2 4 2 4 6 2Output 2 10 |
Public data
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set