Winter is coming
All submissions for this problem are available.
It is a very bad time in the North. Lord Eddard Stark has been killed, the castle has been destroyed and Lady Catelyn is not in the kingdom. To add to the difficulties, “Winter is Coming”. The kingdom of North is composed of houses and roads connecting these houses.
Winters in the North are very harsh and it becomes almost impossible to leave your house. So, this time, the King in the North has devised an intelligent plan
of converting some of the existing roads into tunnels, so that people can walk freely inside them and move from any place to another place i.e. for each house there is a path to every other house through the tunnels. For this he hires some builders to complete this task. All of them submit a plan. The king has to decide which builder to give the contract to.The King will choose the contractor which submits a plan with the minimum cost. Now you need to tell whether the King can decide and choose one of the contractors deterministically or not.
The first line contains two space separated integers N M where
- N: The number of houses
- M: The number of roads
The next M lines contain three space separated integers A B R each, which denotes that cost of constructing a tunnel between houses A and B is R.
Assume that the tunnels are bidirectional.
One line containing “YES” (without quotes) if the King can choose deterministically otherwise "NO" (without quotes).
- 1 ≤ N ≤ 105
- 1 ≤ M ≤ min(2*105, N*(N-1)/2)
- 0 ≤ A,B ≤ N-1
- 1 ≤ R ≤ 109
Input: 4 4 0 1 100 1 2 5 1 3 70 2 3 1000 Output: YES
|Time Limit:||0.151515 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions