Pagini recente » Cod sursa (job #2419441) | Cod sursa (job #1838946) | Cod sursa (job #2388628) | Rating Luca Denisa (deniluca) | Cod sursa (job #2420247)
//#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;
}