source: proiecte/pgraph/Code/Prim/apm.cpp @ 129

//Author Antonio-Gabriel Sturzu

#include<stdio.h>
#include<vector>
#include<string.h>
#include<time.h>
#define pb push_back
#define mp make_pair
#define inf 1001

using namespace std;

int main()
{
        int n,m,a,b,c,cost=0,prev[200001],key[200001],i,min=0,imin=0;
        vector< pair<int,int> > v[200001];
        char viz[200001];
        clock_t time1,time2;
        FILE *f=fopen("apm.in","r");

        fscanf(f,"%i%i",&n,&m);
        for(i=0;i<m;i++)
        {
                fscanf(f,"%i%i%i",&a,&b,&c);
                v[a].pb(mp(b,c));
                v[b].pb(mp(a,c));
        }
        fclose(f);

        memset(viz,0,sizeof(viz));
        time1=clock();
        key[1]=0;
        for(i=2;i<=n;i++)
                key[i]=inf;

        for(;;)
        {
                min=inf;
                for(i=1;i<=n;i++)
                {
                        if(viz[i]==0 && key[i]<min)
                        {
                                min=key[i];
                                imin=i;
                        }
                }
                if(min==inf)
                        break;
                viz[imin]=1;
                cost+=min;
                for(i=0;i<(int) v[imin].size();i++)
                {
                        if(viz[v[imin][i].first]==0 && v[imin][i].second<key[v[imin][i].first])
                        {
                                prev[v[imin][i].first]=imin;
                                key[v[imin][i].first]=v[imin][i].second;
                        }
                } 
        }
        time2=clock();
        printf("Au trecut %f secunde \n",(double)(time2-time1)/CLOCKS_PER_SEC);
        f=fopen("apm.out","w");
        fprintf(f,"%i\n",cost);
        fprintf(f,"%i\n",n-1);
        for(i=2;i<=n;i++)
                fprintf(f,"%i %i\n",prev[i],i);
        fclose(f);
        return 0;
}