Bit masking

[poornima lagadapati]

Bit masking means selecting only certain bits from byte(s) that might have many bits set. To examine some bits of a byte, the byte is bitwise "ANDed" with a mask that is a number consisting of only those bits of interest. For instance, to look at the one's digit (rightmost digit) of the variable flags, you bitwise AND it with a mask of one (the bitwise AND operator in C is &):

flags & 1;

To set the bits of interest, the number is bitwise "ORed" with the bit mask (the bitwise OR operator in C is |). For instance, you could set the one's digit of flags like so:

flags = flags | 1;

Or, equivalently, you could set it like this:

flags |= 1;

To clear the bits of interest, the number is bitwise ANDed with the one's complement of the bit mask. The "one's complement" of a number is the number with all its one bits changed to zeros and all its zero bits changed to ones. The one's complement operator in C is ~. For instance, you could clear the one's digit of flags like so:

flags = flags & ~1;

Or, equivalently, you could clear it like this:

flags &= ~1;

Sometimes it is easier to use macros to manipulate flag values.

 

[Himanshi Agarwal]

Bit masking means selecting only certain bits from byte(s) that might have many bits set. To examine some bits of a byte, the byte is bitwise "ANDed" with a mask that is a number consisting of only those bits of interest. For instance, to look at the one's digit (rightmost digit) of the variable flags, you bitwise AND it with a mask of one (the bitwise AND operator in C is &):

flags & 1;

To set the bits of interest, the number is bitwise "ORed" with the bit mask (the bitwise OR operator in C is |). For instance, you could set the one's digit of flags like so:

flags = flags | 1;

Or, equivalently, you could set it like this:

flags |= 1;

To clear the bits of interest, the number is bitwise ANDed with the one's complement of the bit mask. The "one's complement" of a number is the number with all its one bits changed to zeros and all its zero bits changed to ones. The one's complement operator in C is ~. For instance, you could clear the one's digit of flags like so:

flags = flags & ~1;

Or, equivalently, you could clear it like this:

flags &= ~1;

Sometimes it is easier to use macros to manipulate flag values.

Let's see a problem related to the same-

Swamp Thing feels a disturbance in the Green. It seems that Anton Arcane has once again taken over the Rot and is spreading its evil all over the world. A lot of the world's capital cities are feeling the power of the Rot right now. It is Swamp Thing's duty to preserve a balance between the forces of the Green and the Rot. He must travel to each of the cities affected by the Rot as soon as possible. Luckily, he can use the Green's help to travel to cities through special bidirectional roads. However using the Green to travel from one city to another requires a certain amount of energy. Swamp Thing can only expend a certain amount of energy while travelling.

Swamp Thing wants to travel to all of the world's cities in such an order that the sum of the distances he travels is minimized while the total energy he spends travelling through the Green remains under the maximum energy he can spend.

If such a order of cities does not exist print "-1", else print the minimum distance required to be travelled by Swamp Thing.

Note that Swamp Thing always starts from his swamp whose index is 1 in the input.

INPUT:

Each input file with a line containing three integers, n - the number of cities, m - the number of roads between cities through the Green and E - the amount of energy Swamp Thing can spend.

Then m lines follow, each describing a road. Each road is described in the following format:

u v d e - this represents a bidirectional road from u to v having a distance of d and energy spent will be e.

OUTPUT:

Print the minimum distance required to be traveled by Swamp Thing to visit all cities while spending energy <= E. If no such possible path exists, print -1.

CONSTRAINTS:

1 <= n <= 14

1 <= m <= n * (n - 1) / 2

1 <= E <= 100

1 <= dist between cities <= 100000