Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct Con{
- int node, weight;
- bool operator>(const Con & a) const{
- return weight>a.weight;
- //need to sort the same way as usual for priority queue because greater<int> already sorts the value how we want
- }
- };
- int n, m;
- vector<vector<Con>> con;
- int ans;
- vector<bool> visited;
- vector<int> dist;
- priority_queue<Con, vector<Con>, greater<Con>> pq;
- int main(){
- //freopen("prims.in", "r", stdin);
- cin >> n >> m;
- con.resize(n+1);
- visited.resize(n+1);
- dist.resize(n+1, INT_MAX);
- for(int i=0; i<m; i++){
- int a, b, c;
- cin >> a >> b >> c;
- con[a].push_back({b, c});
- con[b].push_back({a, c});
- }
- pq.push({1, 0});
- dist[1] = 0;
- while(!pq.empty()){
- Con cur = pq.top();
- pq.pop();
- if(visited[cur.node]) continue;
- visited[cur.node] = true;
- ans+=cur.weight;
- for(Con next: con[cur.node]){
- if(!visited[next.node] && cur.weight<dist[next.node]){
- dist[next.node] = next.weight;
- //do not need to equal to value of weights combined just the weight of the next one
- pq.push({next.node, dist[next.node]});
- }
- }
- }
- cout << ans << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
