/
Code.cpp
41 lines (41 loc) · 1.09 KB
/
Code.cpp
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
ll vertex ;
VL dis,parent ;
vector < pair < PLL,ll > > graphedge ;
void bellmanford()
{
dis.clear() ;
dis.resize(vertex+5,0);
parent.clear();
parent.resize(vertex+5,-1);
ll x ;
INC(i,1,vertex)
{
x = -1;
INC(j,0,graphedge.size()-1) {
ll startnode = graphedge[j].F.F ;
ll endnode = graphedge[j].F.S ;
ll weight = graphedge[j].S ;
if (dis[startnode] + weight < dis[endnode])
{
dis[endnode] = max(neginf,dis[startnode] + weight);
parent[endnode] = startnode;
x = endnode ;
}
}
}
if ( x == -1 ) cout << "No negative cycle in this graph "<< endl;
else {
INC(i,1,vertex) x = parent[x];
VL path ;
ll cur = x ;
while(1) {
path.PB(cur);
cur = parent[cur] ;
if ( cur == x ) break ;
}
reverse (path.begin(), path.end());
cout << "Negative cycle: ";
INC(i,0,path.size()-1) cout << path[i] << ' ';
cout << endl;
}
}