Pagini recente » Cod sursa (job #190129) | Cod sursa (job #2983358) | Cod sursa (job #2628825) | Istoria paginii runda/splunge0/clasament | Cod sursa (job #1705211)
# include <fstream>
# include <climits>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int maxn = 10000;
int a[maxn][maxn],n,m;
void prim(int r)
{
int i, cheie[maxn], p[maxn], radacina, vizitati[maxn];
radacina = r;
for (i = 1; i <= n; i++)
{
cheie[i] = INT_MAX;
p[i] = 0;
vizitati[i] = 0;
}
vizitati[r] = 1;
int K = 1,suma=0,minim;
int minim_nevizitat, indice_nevizitat;
while (K < n)
{
minim = INT_MAX;
minim_nevizitat = INT_MAX;
indice_nevizitat = 0;
for (i = 1; i <= n; i++)
if (vizitati[i] == 0 && cheie[i] < minim_nevizitat)
{
minim_nevizitat = cheie[i];
indice_nevizitat = i;
}
for (i = 1; i <= n; i++)
if (a[r][i] != INT_MAX )
{
if (a[r][i] < cheie[i] && vizitati[i]==0)
{
p[i] = r;
cheie[i] = a[r][i];
if (cheie[i] < minim_nevizitat)
{
minim_nevizitat = cheie[i];
indice_nevizitat = i;
//minim = cheie[i];
//nod_bun = i;
}
}
}
r = indice_nevizitat;
vizitati[r] = 1;
suma += minim_nevizitat;
K++;
}
g << suma << "\n";
g << n - 1 << "\n";
for (i = 1; i <= n; i++)
if (p[i] != 0)
g << i << " " << p[i] << "\n";
}
int main()
{
f >> n >> m;
int i,j,x,y,z;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
a[i][j] = INT_MAX;
for (i = 1; i <= m; i++)
{
f >> x >> y >> z;
a[x][y] = a[y][x] = z;
}
prim(1);
}