bellman-ford/algorithm-bellmanford.cpp at master · thinkphp/bellman-ford · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/**
 *  Author           -> Adrian Statescu <mergesortv@gmail.com> <http://thinkphp.ch>
 *  Compile          -> g++ -std=c++11 algorithm-bellmanford.cpp -o bell
 */
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define FIN "bellmanford.in"
#define FOUT "bellmanford.out"
#define oo ((1LL<<31)-1)
#define MAXN 50005

using namespace std;

int nodes,
    edges;

vector<pair<int,int > > Graph[ MAXN ];
int distMin[ MAXN ];

queue<int> Queue;
bitset<MAXN> inQueue;
int countInQueue[ MAXN ];
bool negative_cycle = false;

void readData() {

     int x,
         y,
         cost;

     ifstream fin(FIN);

     fin>>nodes>>edges;

     while(edges--){

           fin>>x>>y>>cost;

           Graph[ x ].push_back({y,cost});
     }

     fin.close();
};

void BellmanFord() {

     for(int i = 2; i <= nodes; i++) distMin[ i ] = oo;

     distMin[ 1 ] = 0;

     Queue.push( 1 );

     inQueue[ 1 ] = true;

     while( !Queue.empty() && !negative_cycle) {

            int node = Queue.front();

            Queue.pop();

            inQueue[ node ] = false;

            for(auto it : Graph[ node ]) {

                if(distMin[ it.first ] > distMin[ node ] + it.second) {

                   distMin[ it.first ] = distMin[ node ] + it.second;

                   if(!inQueue[ it.first ]) {

                       if(countInQueue[ it.first ] > nodes) {

                          negative_cycle = true;

                       } else {

                              Queue.push( it.first );

                              inQueue[ it.first ] = true;

                              countInQueue[ it.first ]++;
                       }
                   }
                }
            }
     }
};


void writeData() {

     ofstream fout(FOUT);

     if(negative_cycle)

          fout<<"Ciclu negativ!";

     else {

         for(int i = 2; i <= nodes; i++)

         fout<<distMin[ i ]<<" ";
     }

     fout.close();
};


int main() {

 readData();
 BellmanFord();
 writeData();

 return(0);
};