Pagini recente » Cod sursa (job #2502584) | Cod sursa (job #1211008)
#include <fstream>
#include <vector>
#define DIM 200010
#define INF 2000000000
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector< pair<int, int> > L[DIM], S;
int H[DIM], D[DIM], P[DIM];
pair<int, int> T[DIM];
int n, cost, m, i, dH, c, p, x, y, k, inHeap;
void swap(int &a, int &b) {
int aux = a;
a = b;
b = aux;
}
int main () {
fin>>n>>m;
for (i=1;i<=m;i++) {
fin>>x>>y>>c;
L[x].push_back( make_pair(y, c) );
L[y].push_back( make_pair(x, c) );
}
for (i=2;i<=n;i++)
D[i] = INF;
H[1] = 1;
P[ H[1] ] = 1;
T[1] = make_pair(0, 0);
dH = 1;
D[1] = -INF;
while (1) {
k = H[1];
if (T[k].first != 0) {
S.push_back(make_pair(T[k].first, k));
cost += T[k].second;
if (S.size() == n-1)
break;
}
H[1] = H[dH--];
P[ H[1] ] = 1;
p = 1;
c = 2*p;
while (c <= dH) {
if (c + 1 <= dH && D[ H[c+1] ] < D[ H[c] ])
c++;
if (D[ H[c] ] < D[ H[p] ]) {
swap(H[c], H[p]);
P[ H[c] ] = c;
P[ H[p] ] = p;
p = c;
c = 2*p;
} else
break;
}
for (i=0;i<L[k].size();i++)
if (D[ L[k][i].first ] > L[k][i].second) {
if (D[ L[k][i].first ] == INF)
inHeap = 0;
else
inHeap = 1;
D[ L[k][i].first ] = L[k][i].second;
T[L[k][i].first] = make_pair(k, L[k][i].second);
if (!inHeap) {
dH++;
H[dH] = L[k][i].first;
P[H[dH]] = dH;
}
if (inHeap)
c = P[L[k][i].first];
else
c = dH;
p = c/2;
while (p) {
if (D[ H[c] ] < D[ H[p] ]) {
swap(H[c], H[p]);
P[ H[c] ] = c;
P[ H[p] ] = p;
c = p;
p = p/2;
} else
break;
}
}
}
fout<<cost<<"\n"<<n-1<<"\n";
for (i=0;i<n-1;i++)
fout<<S[i].first<<" "<<S[i].second<<"\n";
return 0;
}