Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<queue>
- #include<string.h>
- using namespace std;
- int n,e,edge[100][100];
- struct node
- {
- int cost, vertex;
- };
- bool operator<(node a, node b)
- {
- return a.cost>b.cost;
- }
- int prims()
- {
- bool visited[100];
- memset(visited, false, sizeof(visited));
- node temp;
- temp.cost=0;
- temp.vertex=0;
- priority_queue<node>pq;
- pq.push(temp);
- int ans=0;
- while(!pq.empty())
- {
- node cur = pq.top();
- pq.pop();
- if(visited[cur.vertex])
- {
- continue;
- }
- visited[cur.vertex] = true;
- ans=ans+cur.cost;
- for(int i=0; i<n; i++)
- {
- if(edge[cur.vertex][i] >=0)
- {
- node t;
- t.cost=edge[cur.vertex][i];
- t.vertex=i;
- if(visited[i] == false)
- {
- pq.push(t);
- }
- }
- }
- }
- return ans;
- }
- int main()
- {
- while(cin>>n>>e)
- {
- for(int i=0; i<n; i++)
- {
- for(int j=0; j<n; j++)
- {
- edge[i][j]=-1;;
- }
- }
- for(int i=0; i<e; i++)
- {
- int a,b,c;
- cin>>a>>b>>c;
- edge[a][b]=c;
- edge[b][a]=c;
- }
- int ans = prims();
- cout<<ans<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement