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.↵
23. It 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↵
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.↵
↵
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