There is an undirected weighted graph. And also, the specified number of possible changes in the weight of the edges of the graph is K and the cost by which the edge weight can be replaced is M.

The task is to calculate what the maximum cost of the passage from the very first vertex to all the others can be achieved with the help of a fixed number of replacements K with cost M. And find the minimum number of substitutions to achieve such a result with the numbers of all modified edges.

For example, there is a graph (it enters the program as edges, each line is a new edge. The very first one contains three numbers N - the number of vertices, K and M ):

7 1 2 1 2 3 1 3 2 1 4 4 1 5 1 6 5 15 7 5 10

graph

For him, the answer will be:

  • maximum fare from 1 to all others - 40
  • Number of replacements required - 1
  • edge numbers on which weights need to be replaced

Here, it is advantageous to change the weight of the edge from the 1st vertex to the 5th. The maximum cost is calculated as follows: 3 + 2 + 4 + 2 + (15 + 2) + (10 + 2) = 40

I tried to solve it this way: by traversing the graph in depth, we find the number of child vertices of each vertex, and then take from them the top with the largest number of children. But in particular cases, this approach does not work.

Prompt ways to solve the problem.

Closed due to the fact that off-topic participants 0xdb , VTT , tym32167 , nick_n_a , freim Jan 24 at 10:56 .

It seems that this question does not correspond to the subject of the site. Those who voted to close it indicated the following reason:

  • " Learning tasks are allowed as questions only on the condition that you tried to solve them yourself before asking a question . Please edit the question and indicate what caused you difficulties in solving the problem. For example, give the code you wrote, trying to solve the problem "- 0xdb, VTT, tym32167, nick_n_a, freim
If the question can be reformulated according to the rules set out in the certificate , edit it .

  • 1. Regarding the traversal of the graph, it always seemed to me that only two ways - in width and in depth. (you can still the same with a width / depth limitation, I think it is unacceptable here) 2. If you solve the problem 1 - max fare - why do you choose max-quo-vertices? Calculate in the course immediately fare, bring it in max, the calculated value drop before the next passage. - nick_n_a
  • Those. that's right, the longest (max tops) path is not always the most expensive. - nick_n_a

0