Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- ifstream fin ("bellmanford.in");
- ofstream fout ("bellmanford.out");
- int N, M, x, y, c;
- const int maxn = 50005;
- const int INF = 0x3f3f3f3f;
- vector < pair < int , int > > G[maxn];
- int main () {
- fin >> N >> M;
- while (M --) {
- fin >> x >> y >> c;
- G[x].push_back ({y, c});
- }
- queue < int > Q;
- bitset < maxn > inQ (false);
- vector < int > dist (maxn, INF), cntinQ (maxn, 0);
- bool ciclu_negativ = false;
- dist[1] = 0, Q.push (1), inQ[1] = true;
- while (!Q.empty() && !ciclu_negativ) {
- int x = Q.front ();
- Q.pop ();
- inQ[x] = false;
- vector < pair < int , int > > :: iterator it;
- for (it = G[x].begin(); it != G[x].end(); ++it)
- if (dist[x] < INF)
- if (dist[it -> first] > dist[x] + it -> second) {
- dist[it -> first] = dist[x] + it -> second;
- if (!inQ[it -> first]) {
- if (cntinQ[it -> first] > N) ciclu_negativ = true;
- else {
- Q.push (it -> first);
- inQ[it -> first] = true;
- cntinQ[it -> first] ++;
- }
- }
- }
- }
- if (!ciclu_negativ) for (int i = 2; i <= N; i ++) fout << dist[i] << ' ';
- else fout << "Ciclu negativ!\n";
- fin.close ();
- fout.close ();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement