Cod sursa(job #3373351)

Utilizator TLuca2021Teodorescu Luca Nicolae TLuca2021 Data 6 noiembrie 2026 17:20:51
Problema Arbore partial de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include<fstream>
#include<vector>
#include<queue> 
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct Edge{
    int first;
    int second;
    int cost;
    bool operator>(const Edge &other) const {
        if(cost == other.cost){
            if(first == other.first){
                return second > other.second;
            }
            return first > other.first;
        }
        return cost > other.cost;
    }
};
struct Node{
    int node;
    int cost;
};
int main(){
    int n, m, result = 0;
    fin >> n >> m;
    vector<vector<Node>> adj(n, vector<Node>());
    vector<bool> visited(n, false);
    for(int i = 0; i < m; i++){
        int first_node, second_node, cost;
        fin >> first_node >> second_node >> cost;
        first_node--;
        second_node--;
        adj[first_node].push_back({second_node, cost});
        adj[second_node].push_back({first_node, cost});
    }
    visited[0] = true;
    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
    for(auto it : adj[0]){
        int node = it.node;
        int cost = it.cost;
        pq.push({0, node, cost});
    }
    while(!pq.empty()){
        Edge top = pq.top();
        pq.pop();
        if(visited[top.second] == true){
            continue;
        }
        visited[top.second] = true;
        result += top.cost;
        for(auto it : adj[top.second]){
            if(visited[it.node] == false){
                pq.push({top.second, it.node, it.cost});
            }
        }
    }
    fout << result << '\n';
    return 0;
}