Cod sursa(job #2420247)

Utilizator dadada876Cinca Adrian dadada876 Data 11 mai 2019 12:36:11
Problema Arbore partial de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
//#include "pch.h"
#include <iostream>
#include<fstream>
#include<queue>
#include<vector>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
vector<pair<int, pair<int, int>>> v,t;
vector<pair<int, int>> graph[100005];
priority_queue< pair<int, pair<int, int>>> pq;


int main()
{
	int N, M, X, Y, C, s = 0;
	f >> N >> M;
	for (int i = 0; i < M; i++) {
		f >> X >> Y >> C;
		v.push_back(make_pair(-C, make_pair(X, Y)));
		graph[X].push_back(make_pair(-C, Y));
		graph[Y].push_back(make_pair(-C, X));
	}
	int viz[100005];
	for (int i = 1; i <= N; i++)
		viz[i] = 0;
	for (int i = 0; i < graph[1].size(); i++) {
		int cost, vecin;
		cost = graph[1][i].first;
		vecin = graph[1][i].second;
		pq.push(make_pair(cost, make_pair(1, vecin)));

	}
	viz[1] = 1;
	while (!pq.empty()) {
		int cost, vecin, nod;
		pair<int, pair<int, int>> best;
		best=pq.top();
		cost = best.first;
		vecin = best.second.second;
		nod = best.second.first;
		pq.pop();
		if (viz[nod] && viz[vecin])
			continue;
		else
		{
			s++;
			if (!viz[vecin]) {
				t.push_back(best);
				int size = graph[vecin].size();
				for (int i = 0; i < size; i++) {
					int vec, cst;
					vec = graph[vecin][i].second;
					cst = graph[vecin][i].first;
					pq.push(make_pair(cst, make_pair(vecin,vec)));
				}
				viz[vecin] = 1;
			}
			if (!viz[nod]) {
				t.push_back(best);
				int size = graph[nod].size();
				for (int i = 0; i < size; i++) {
					int vec, cst;
					vec = graph[nod][i].second;
					cst = graph[nod][i].first;
					pq.push(make_pair(cst, make_pair(vecin, vec)));
				}
				viz[nod] = 1;
			}
		}

	}

	int suma = 0;
	for (int i = 0; i < s; i++)
		suma = suma -t[i].first;

	cout << suma;
	/*while (!pq.empty()) {
		cout << pq.top().second.second << ' ';
		pq.pop();
	}
	*/
	return 0;
}