AROAD - Another Road Problem
Problem
Let's say you are given a set of cities (numbered from 1 to n) and possible bidirectional roads between them. You would like to build cheapest road network that will make getting from the capital (which has number 1) to every other city possible, where the cost of the network is just sum of its roads' costs. Seems easy? Well, it certainly would be too easy and boring, so this time you should satisfy one additional constraint: you must consider only networks in which there are at most d roads outgoing from the capital.
Input
First line of input contains number of test cases c (1<=c<=40). Each test case begins with number of cities n, number of possible roads m and maximum degree d (1<=n<=1000, 0<=m<=100000, 0<=d<=100). Then m lines describing roads follow, each of them containing road endpoints x, y and its cost c (1<=x, y<=n, 0<=c<=10000).
Output
For each test case output the cost of building cheapest road network or NONE if it is impossible.
Example
Input: 4 4 5 0 1 2 1 1 3 1 1 4 2 2 3 2 3 4 1000 4 5 1 1 2 1 1 3 1 1 4 2 2 3 2 3 4 1000 4 5 2 1 2 1 1 3 1 1 4 2 2 3 2 3 4 1000 4 5 3 1 2 1 1 3 1 1 4 2 2 3 2 3 4 1000 Output: NONE 1003 5 4
hide comments
:D:
2011-04-15 19:09:12
n can't be 0, read the constraints. If you can't make a spanning tree with the given limit the answer is NONE. m=0 is no special case needing additional explanation. |
|
Chairaja Almas Djeni:
2011-01-23 18:31:42
what if the number of road is 0??
|
|
tʰɒŋ toŋ ʨĩ:
2010-06-23 05:22:55
Soenfeah:
|
Added by: | gawry |
Date: | 2005-10-07 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS PERL6 VB.NET |