Pagini recente » Borderou de evaluare (job #1515734) | Cod sursa (job #1357294)
#include<fstream>
using namespace std;
#define INF 32000
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,costs[100],C[100],p[100];
int a[100][100];
void citire()
{
fin>>n>>m;
int x,y,c,i;
for(i=1;i<=m;i++)
{
fin>>x>>y>>c;
a[x][y]=c;
a[y][x]=c;
}
int r=1;
for(i=1;i<=n;i++)
{
if(a[r][i])
{costs[i]=a[r][i];}
else costs[i]=INF;
C[i]=1; p[i]=r;
}
C[r]=0;
p[r]=0;
fin.close();
}
void rezolva()
{
int i;
for(int j=1;j<n;j++)
{
int aux=INF,minv=-1;
for(i=1;i<=n;i++)
if(C[i] && aux>costs[i])
{ aux=costs[i]; minv=i;}
C[minv]=0;
for(i=1;i<=n;i++)
if(C[i] && a[minv][i]<costs[i] && a[minv][i])
{p[i]=minv; costs[i]=a[minv][i];}
}
}
void afisare(int r)
{
int i,sum=0,much=0;
for(i=1;i<=n;i++)
if(i!=r && a[p[i]][i])
{
sum+=costs[i];
much++;}
fout<<sum<<"\n"<<much<<"\n";
for(i=1;i<=n;i++)
if(i!=r && a[p[i]][i])
fout<<p[i]<<" "<<i<<"\n";
fout.close();
}
int main()
{
citire();
rezolva();
afisare(1);
return 0;
}