Graph problem to minimise total distance from all nodes to a source node under constraints.
Difference between en1 and en2, changed 86 character(s)
I was solving some graph problems with dp and bitmasking when a problem crossed my mind.↵
But I'm unable to solve it optimally. I tried brute force considering all possible combinations. Can we form an optimal solution?↵

The problem goes like this: ↵

`SPECIAL node` : Can connect upto 10 nodes.↵

`GOOD node`: Is only connected to exactly 1 `SPECIAL node` and no other node.↵

`VALID edge`: Has atleast one `SPECIAL node`.↵

`VALID graph`: A connected graph such that every edge is a `VALID edge` and each node is either a `GOOD node` or a `SPECIAL node`.↵

Given a connected graph with `N` nodes (including a `source` node), your task is to:↵

1. Delete 0 or more edges such that the graph becomes a `VALID graph`.↵
2. And the sum of distances from all nodes to source node is minimum.↵
3. And the number of `SPECIAL nodes` is minimum possible.↵

Note:↵

1. Graph is undirected.↵
2. It is always possible to connect all nodes.
23It is always possible to connect allMinimisation of sum has higher priority than minimisation of `SPECIAL nodes`.↵

Constraints:↵

~~~~~↵
1<N<=30↵
1<=E<=435↵
1<=src<=30↵
~~~~~↵



Input:↵
`N` -> total number of nodes↵

`E` edges with values: `u v w` (there is an edge between u and v with length w)↵

`src` -> index of source node

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English dragoneel 2018-11-12 11:40:30 86
en1 English dragoneel 2018-11-10 17:45:34 1257 Initial revision (published)