Check this: if (!used[j] and min_e[j] < min_e[v] and j!=v) {

Edited by author 23.03.2022 22:57

This is not an MST problem, because finally, we can have a graph with several connected components (not a tree). For example, if a city has a power station and the price to build a line to another city is too high we can just isolate this city. Such test:
4 2
1 4
0 1 1 7
1 0 5 2
1 5 0 2
7 2 2 0

The answer is 2.
We build line 1 <-> 2, 1 <-> 3. The total price is 2. It's not necessary to build any line to city 4.

I don't know, maybe there are no tests for such cases.


Edited by author 09.10.2019 16:52

Hello,
I didn't understand the problem statement correctly. Do cities having power stations need to be connected to each other? The solution can be also having more than 1 connected components( Graphs ), right?

Edited by author 21.09.2017 09:28

Edited by author 21.09.2017 09:32

I have implemented a greedy algorithm to solve this problem and it got accepted and after reading the discussion I have noticed that many people used Prims algorithm to solve.
I have no idea of what Prims algorithm is. Could anyone please tell me what exactly is my code doing and how is it different from Prims algorithm?

[code deleted]

Edited by moderator 21.01.2020 16:06

Can anybody please give me cases for Test2 ?

in prims algo implementation using priority queue, how can i decrease a key in priority queue ?

Can anybody give some hits or information on test 28, thanks!

use prim or kruskal can solve it.

First I used Kruskal algo but got WA9 verdict.
My program didn't give right answer for next test:
4 1
4
0    1    1    100000
1    0    1    100000
1    1    0    100000
100000    100000    100000    0
right answer:
100002

Implementation of Prim algo gave the correct answer at last.