Description

The Data Structure TAs are trying to set a video streaming service in campus. There are several buildings in the campus, we want to stream to all of them from building '0'. We want to find the"optimal" way to stream to each destination from our source building '0'. Luckily, this is equivalent to building a Minimum Spanning Tree!

You will be given M connections for N buildings. Each connection is specified by: source building, destination building, latency and bandwith. You should first build a graph with the buildings as nodes, and connections as edges. You should then build the minimum spanning tree. Finally, you should find the Min-Latency and Max-Latency for each building, where:

• The Min Latency to a destination building is: The minimum latency sum (ie.sum of the latencies from all edges in the path)  from all paths from destination to source
• The Max Bandwith to a destination building is: the bottleneck along the path from source to destination (ie. the edge along the path with minimum bandwith, which will be the bottleneck)

An example of the Graph, Minimum Latency and Max Bandwith is given below:

Input

• An integer n, the number of buildings (n<1000)
• An integer m, the number of candidate connections
• M lines with the candidate connections, each line will have 4 integers, which represent:
  • source building number, destination building number, Min Latency, Max Bandwith; separated with withespaces, with newlines at the end, where:
    • 0<Latency<11
    • 0<Bandwith<31
  • 

Output

• N-1 lines, one for each building except for the source, building '0', with 3 integers:
  • Building no., Min Latency, Max Bandwith; separated witht whitespaces, with newline at the end.
• Note:
  • For an unconnected building, Min latency will be the 3 character string "inf", and Max Bandwith will be '0'

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss