| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12291 | Video Streaming Network Quiz |
|
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, solving this problem is equivalent to building a Minimum Spanning Tree!
You will be given M connections for N buildings. Each building is specified by its latency (ie. this time, not only edges have latency, but buildings too). 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 for each building, that is the minimum latency sum (ie.sum of the latencies from all edges in the path) from all paths from destination to source (including both source and destination stations).
An example of the Graph and Minimum Latency is given below:
Input
- An integer n, the number of buildings (n<1000)
- N lines with the latencies of buildings 0 - N-1
- An integer m, the number of candidate connections
- M lines with the candidate connections, each line will have 3 integers, which represent:
- source building number, destination building number, Min Latency; separated with withespaces, with newlines at the end, where: 0<Latency<11
Output
- N-1 lines, one for each building except for the source, building '0', with 2 integers:
- Building no. and Min Latency; separated witht whitespaces, with newline at the end.
- Note:
- For an unconnected building, Min latency will be the 3 character string "inf".