Cod sursa(job #2466888)

Utilizator LXGALXGA a LXGA Data 3 octombrie 2019 10:10:18
Problema Arbore partial de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
queue<int> q;
vector<pair<int,int>> v[200001];
vector<pair<int,int>> ans;
int n,m;
int use[200001];
int sum;
void bfs(int pos)
{
    for(int i=1;i<=200000;i++)
        use[i]=-1001;
    q.push(pos);
    use[pos]=1;
    while(q.size()>0)
    {
        for(int i=0; i<v[q.front()].size(); i++)
        {
            if(use[v[q.front()][i].first]==-1001)
            {
                q.push(v[q.front()][i].first);
                sum+=v[q.front()][i].second;
                use[v[q.front()][i].first]=v[q.front()][i].second;
                ans.push_back()
            }
            else if(v[q.front()][i].second<use[v[q.front()][i].first])
            {
                sum-=use[v[q.front()][i].first];
                sum+=v[q.front()][i].second;
                use[v[q.front()][i].first]=v[q.front()][i].second;
            }
        }
        q.pop();
    }

}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y,c;
        cin>>x>>y>>c;
        v[x].push_back({y,c});
        v[y].push_back({x,c});
    }
    bfs(1);
    cout<<sum;
    return 0;
}