Hello, 'Temp.
I've been stuck on this problem for 2 hours or so without any ideas...
The way it goes is that you have an unoriented multi-graph with N vertices and M links between them.
Each link has its own length.
Every combination of vertices has a number of Xs(let's call 'em that) wanting to get from the first vertex to the second and from the second to the first.
You need to choose N-1 of these M links, so that both of these conditions are met:
1. There is a way to get from any vertex to all others. (easy as pie)
2. The links need to be chosen in such a way that the travelled distance of all Xs is minimal in comparison to all other combinations.
I've already solved it via DFS (Depth-First Search), but it's just too slow.
I know there is a faster method, but I can't think of it for the likes of me.
If anyone can post a solution, I'll be extremely thankful.
Just saying that this must be written in C++.
And to those who might be asking: No, this is not homework.
I've been stuck on this problem for 2 hours or so without any ideas...
The way it goes is that you have an unoriented multi-graph with N vertices and M links between them.
Each link has its own length.
Every combination of vertices has a number of Xs(let's call 'em that) wanting to get from the first vertex to the second and from the second to the first.
You need to choose N-1 of these M links, so that both of these conditions are met:
1. There is a way to get from any vertex to all others. (easy as pie)
2. The links need to be chosen in such a way that the travelled distance of all Xs is minimal in comparison to all other combinations.
I've already solved it via DFS (Depth-First Search), but it's just too slow.
I know there is a faster method, but I can't think of it for the likes of me.
If anyone can post a solution, I'll be extremely thankful.
Just saying that this must be written in C++.
And to those who might be asking: No, this is not homework.
