Cod sursa(job #2328027)

Utilizator testEMTest Surse testEM Data 25 ianuarie 2019 12:22:49
Problema Arbore partial de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m;
vector <int> v[200005];
vector <int> costuri[200005];
bool bifat[200005];

queue <int> q;

int cost = 0;

int main()
{
    f >> n >> m;

    for(int i = 1 ; i <= m ; i++){
        int x, y, c;
        f >> x >> y >> c;
        v[x].push_back(y);
        v[y].push_back(x);
        costuri[x].push_back(c);
        costuri[y].push_back(c);
    }

    int i = 1;
    q.push(i);
    while(!q.empty()){
        i = q.front();
        for(int j = 1 ; j <= v[i].size() ; j++){
            int minim = 2000;
            for(int k = 1 ; k <= v[v[i][j]].size() ; j++){
                if(minim >= costuri[v[i][j]][k] && bifat[v[v[i][j]][k]] == 0){
                    minim = costuri[v[i][j]][k];
                }
            }
            if(costuri[i][j] < minim){
                cost += costuri[i][j];
                bifat[v[i][j]] = 1;
                q.push(v[i][j]);
            }
        }

        for(auto it : v[i]){
            int minim = 2000;
            for(auto itt : v[it]){
                if(minim > itt && bifat[it][itt] == 0){
                    minim = itt;
                }
            }

            if()
        }
        q.pop();
    }

    g << cost;
    return 0;
}