iGraphics Files iGraphics Files (Updated 2017) Visual Studio 13 Professional iGraphics Tutorial in Bangla Subscribe to my YouTube channel Sayef Reyadh - Programming Made Simple Character Collection Disclaimer : These characters sprite sheet is copyrighted to their respected owners. This should only be used as Fair Use Act Disclaimer . Copyright Disclaimer under section 107 of the Copyright Act 1976, allowance is made for “fair use” for purposes such as criticism, comment, news reporting, teaching, scholarship, education and research.
/* created by */
ReplyDelete#include
using namespace std;
#define f(i,n) for(int i=0;i > > graph;
priority_queue< pair > pq;
bool visited[NODES]={false};
int vertex, edge;
int prim(int source){
pq.push(make_pair(0, source)); // (weight, cost) // we have to negate as cpp has max-PQ and we need min-PQ
int total_cost=0; // the total cost
while(!pq.empty()){
auto pair_=pq.top(); pq.pop();
int node = pair_.second; int cost=-pair_.first; // - - = +
if(visited[node])
continue;
visited[node]=true;
total_cost+=cost;
// now we visit all the child nodes of the current node
for(auto &children:graph[node]){
if(visited[children.first])
continue;
pq.push(make_pair(-children.second,children.first)); // we negate as we need min-PQ // here children.second comes first
}
}
return total_cost;
}
int main()
{
cin >> vertex >> edge;
f(i,edge){
int to,from,weight; cin>>to>>from>>weight;
graph[to].emplace_back(make_pair(from, weight));
graph[from].emplace_back(make_pair(to,weight));
}
int source;cin>>source; // if source is given
// cout << "MST is " << prim(source) << "\n";
cout << prim(source) << "\n";
return 0;
}