All submissions for this problem are available.
You are given an undirected graph with N nodes and M edges. Each edge has a cost associated with it and is colored either black or white. You need to find a spanning tree with minimum cost such that for every path in the tree, the color of edges is alternating. The cost of the spanning tree is the sum of cost of edges in it.
Print the minimum cost.
The first line of input contains 2 integers N (2 <= N <= 18) and M (1 <= M <= 306), the number of nodes and the number of edges.
Each of the next M lines describe an edge. Each line contains three integers U, V, C and a character S(1 <= U, V <= N, 1 <= C <= 10^9) - there is an edge between U and V with cost C. If S equal 'W' then the edge is colored white. Otherwise S equals 'B' and edge is colored black. The graph doesn't have any self loops.
Output a single integer, the minimum cost of the spanning tree. If no such spanning tree exists then output -1.
- 2 ≤ N ≤ 18
- 1 ≤ M ≤ 306
- 1 ≤ U, V ≤ N
- 1 ≤ C ≤ 10^9
Input: 3 4 1 2 2 B 1 2 3 W 2 3 4 W 2 3 5 B Output: 6
|Time Limit:||- 3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.