Rev | Line | |
---|
[129] | 1 | //Author Antonio-Gabriel Sturzu |
---|
| 2 | |
---|
| 3 | #include<stdio.h> |
---|
| 4 | #include<vector> |
---|
| 5 | #include<omp.h> |
---|
| 6 | #define pb push_back |
---|
| 7 | #define mp make_pair |
---|
| 8 | #define inf 0x3f3f3f3f |
---|
| 9 | |
---|
| 10 | using namespace std; |
---|
| 11 | |
---|
| 12 | int main() |
---|
| 13 | { |
---|
| 14 | int n,m,i,j,k,a,b,c,d[50001],flag=0; |
---|
| 15 | vector < pair<int,int> > v[50001]; |
---|
| 16 | double start,stop; |
---|
| 17 | FILE *f=fopen("bell.in","r"); |
---|
| 18 | |
---|
| 19 | fscanf(f,"%i%i",&n,&m); |
---|
| 20 | for(i=0;i<m;i++) |
---|
| 21 | { |
---|
| 22 | fscanf(f,"%i%i%i",&a,&b,&c); |
---|
| 23 | v[a].pb(mp(b,c)); |
---|
| 24 | } |
---|
| 25 | fclose(f); |
---|
| 26 | |
---|
| 27 | start=omp_get_wtime(); |
---|
| 28 | d[1]=0; |
---|
| 29 | for(i=2;i<=n;i++) |
---|
| 30 | d[i]=inf; |
---|
| 31 | |
---|
| 32 | for(i=0;i<n-1;i++) |
---|
| 33 | { |
---|
| 34 | flag=0; |
---|
| 35 | for(j=1;j<=n;j++) |
---|
| 36 | { |
---|
| 37 | #pragma omp parallel shared(d,j,v) private(k) |
---|
| 38 | { |
---|
| 39 | #pragma omp for schedule(static) reduction(|:flag) |
---|
| 40 | for(k=0;k<(int) v[j].size();k++) |
---|
| 41 | { |
---|
| 42 | if(d[j]+v[j][k].second<d[v[j][k].first]) |
---|
| 43 | { |
---|
| 44 | d[v[j][k].first]=d[j]+v[j][k].second; |
---|
| 45 | flag=1; |
---|
| 46 | } |
---|
| 47 | } |
---|
| 48 | } |
---|
| 49 | } |
---|
| 50 | if(flag==0) |
---|
| 51 | break; |
---|
| 52 | } |
---|
| 53 | stop=omp_get_wtime(); |
---|
| 54 | printf("Au trecut %f secunde\n",stop-start); |
---|
| 55 | f=fopen("bell2.out","w"); |
---|
| 56 | for(i=2;i<=n;i++) |
---|
| 57 | { |
---|
| 58 | if(d[i]==inf) |
---|
| 59 | d[i]=0; |
---|
| 60 | fprintf(f,"%i ",d[i]); |
---|
| 61 | } |
---|
| 62 | fprintf(f,"%s","\n"); |
---|
| 63 | fclose(f); |
---|
| 64 | return 0; |
---|
| 65 | } |
---|
Note: See
TracBrowser
for help on using the repository browser.