Pagini recente » Cod sursa (job #531415) | Cod sursa (job #2949098)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
#if 0
#define cin fin
#define cout fout
#endif
using vi = vector<int>;
using pi = pair<int,int>;
using vpi = vector<pi>;
const int nmx = 2e5+1;
const int inf = 1e7;
vpi a[nmx];
int d[nmx],t[nmx];
int main()
{
int n,m;
fin >> n >> m;
while(m--)
{
int u,v,c;
fin >> u >> v >> c;
a[u].emplace_back(v,c);
a[v].emplace_back(u,c);
}
set<pi> q; // value, vertex
fill(d,d+nmx,inf);
q.emplace(0,1);
d[1] = 0;
vpi res;
int cost = 0;
for(int kk=0;kk<n;kk++)
{
if(q.empty())
{/// no mst
cout << kk;
return -1;
}
auto it = q.begin();
int v = it->second;
int c = it->first;
res.emplace_back(t[v],v);
cost += c;
q.erase(it);
d[v] = -1;
for(pi& to : a[v])
{
if(d[to.first] > to.second && d[to.first] !=-1)
{
q.erase({d[to.first],to.first});
d[to.first] = to.second;
t[to.first] = v;
q.emplace(d[to.first],to.first);
}
}
}
fout << cost << "\n" << n-1 << "\n";
for (int i=1;i<res.size();i++)
fout << res[i].first << " " << res[i].second << "\n";
}