source: proiecte/pgraph/Code/Bellman-Ford/pbell2.cpp @ 129

//Author Antonio-Gabriel Sturzu

#include<stdio.h>
#include<vector>
#include<omp.h>
#define pb push_back
#define mp make_pair
#define inf 0x3f3f3f3f

using namespace std;

int main()
{
        int n,m,i,j,k,a,b,c,d[50001],flag=0;
        vector < pair<int,int> > v[50001];
        double start,stop;
        FILE *f=fopen("bell.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));
        }
        fclose(f);

        start=omp_get_wtime();
        d[1]=0;
        for(i=2;i<=n;i++)
                d[i]=inf;

        for(i=0;i<n-1;i++)
        {
                flag=0;
                for(j=1;j<=n;j++)
                {
                        #pragma omp parallel shared(d,j,v) private(k)
                        {
                                #pragma omp for schedule(static) reduction(|:flag)
                                for(k=0;k<(int) v[j].size();k++)
                                {
                                        if(d[j]+v[j][k].second<d[v[j][k].first])
                                        {
                                                d[v[j][k].first]=d[j]+v[j][k].second;
                                                flag=1;
                                        }
                                }
                        }
                }
                if(flag==0)
                        break;
        }
        stop=omp_get_wtime();
        printf("Au trecut %f secunde\n",stop-start);
        f=fopen("bell2.out","w");
        for(i=2;i<=n;i++)
        {
                if(d[i]==inf)
                        d[i]=0;
                fprintf(f,"%i ",d[i]);
        }
        fprintf(f,"%s","\n");
        fclose(f);
        return 0;
}