Pagini recente » Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #2493468) | Rezultatele filtrării | Cod sursa (job #2498819)
#include <bits/stdc++.h>
using namespace std;
ifstream f("prim.in");
ofstream h("prim.out");
int n,r,nrv,cost,muchii;
int g[100][100];
int cmin[100];
bool Z[100];
int p[100];
void Initializare()
{
f>>n>>r;
int x,y,cost;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(i!=j) g[i][j] = INFINITY;
while(f>>x>>y>>cost)
g[x][y]=g[y][x] = cost;
for(int i=1;i<=n;++i)
{
cmin[i] = g[r][i];
p[i] = r;
}
Z[r] = true;
p[r] = 0;
nrv = n-1;
f.close();
}
void Afisare()
{
h<<cost<<'\n'<<muchii<<'\n';
for(int i=1;i<=n;++i)
if(i!=r)
h<<p[i]<<" "<<i<<'\n';
}
int main()
{
Initializare();
while(nrv)
{
int CostMin = INFINITY,VfMin;
for(int i=1;i<=n;++i)
if(Z[i] == false && CostMin >cmin[i])
{
CostMin = cmin[i];
VfMin = i;
}
Z[VfMin] = true;
cost += CostMin;
nrv--;
++muchii;
for(int i=1;i<=n;++i)
if(Z[i] == false && g[i][VfMin] < cmin[i])
{
p[i] = VfMin;
cmin[i] = g[i][VfMin];
}
}
Afisare();
return 0;
}