revised-locter/Prim's Algorithm at main · rishabh-stack/revised-locter · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e4 + 5;
vector<pair<long long,int>> adj[MAX];
bool marked[100];


int prim(int x)
{
    priority_queue<int,vector<pair<long long,int>>,greater <pair<long long,int>>>q;
    q.push({0,x});
   long long minimumCost=0;
   pair<long long,int> p;
   int y;
   while(!q.empty())
   {
       p=q.top();
       q.pop();
       x=p.second;
       if(marked[x]==true)
            continue;
        cout<<p.first<<" "<<p.second<<endl;
        minimumCost+=p.first;
       marked[x]=true;
       for(int i=0;i<adj[x].size();i++)
       {
          if(!marked[adj[x][i].second])
          {
              q.push(adj[x][i]);
          }
       }
   }
   return minimumCost;
}
int main()
{
  int nodes, edges, x, y;
    long long weight, minimumCost;
    cin >> nodes >> edges;
    for(int i = 0;i < edges;++i)
    {
        cin >> x >> y >> weight;
        adj[x].push_back(make_pair(weight, y));
        adj[y].push_back(make_pair(weight, x));
    }
    // Selecting 1 as the starting node
    minimumCost = prim(1);
    cout << minimumCost << endl;
    return 0;
}