×

EASY

# EXPLANATION

Obviously, all the roads that will be profitable should be decorated. So we will include them in the answer at the very beginning. Then we can sort the rest of edges by their cost and apply the following greedy approach: if the edge connects two connected components and there is no restaurant in at least one of these components then this edge should be included into the answer and the components should be merged. Merging components can be done by union-find data structure. Another similar approach is to connect all the restaurants in the very beginning, after including the edges with negative weight and simply build a mst then. Also pay attention that the upper bound of the answer may fit into int but the lower bound of the answer could be about -8*10^9 so 64-bit type should be used for storing the answer(long long in C++, int64 in Pascal).

# SETTER'S SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

15.4k347484505
accept rate: 35%

 0 What is the o/p of the following case? 1 4 3 HRHR 1 2 3 2 3 2 3 4 -1  My AC solution is giving 2, but i think it is 4. answered 10 Mar '15, 17:53 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×10,863
×2,522
×8
×2

question asked: 22 Nov '12, 12:17

question was seen: 3,170 times

last updated: 10 Mar '15, 17:54