All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
There are N servers which you have to place in N slots. Slots and servers are numbered from 1 to N.
A distance between slots i and j is |i - j|. There are M pairs of servers that should be connected by wire. You are to place all the servers in the slots so the total wire length is minimized.
The first line of the input contains two integer numbers N and M. Then M lines follow. Each of them contains two numbers a and b, which means that server a and server b should be connected to each other.
Output single integer — minimal wire length required to connect all the servers arranged in N slots.
1 ≤ N ≤ 20
0 ≤ M ≤ N * (N - 1) / 2
Input: 3 2 1 2 1 3 Output: 2
One of the optimal arrangements is [2, 1, 3]
|Tags||Rubanenko, cook53, dp+bitmask, medium|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.