### Vedkribhu's blog

By Vedkribhu, history, 13 months ago,

Problem: Link I was using Bellman Ford to solve this. To detect a cycle in bellman ford we usually do one more pass on the edges (after n-1) passes and see if anything updated, if yes there is a cycle. But in this problem even if there is a cycle in graph but not a part of path between vertex 1 and n is tolerable. How to detect when to print -1?

• 0

 » 13 months ago, # |   +2 Run the Bellman-Ford Algorithm for the nth iteration and mark the nodes whose distance is changed. Now reverse the adjacency list and run a DFS from node 'n'. If at least one of the nodes marked is visible from n, then the answer is -1, else the answer is the maximum distance from 1 to n.
•  » » 13 months ago, # ^ |   0 Can you please explain the intuition behind doing this?
•  » » » 11 months ago, # ^ |   0 Only to check that, does a positive cycle in the graph affects the 'nth' node, if it does, then it is sure that answer is -1, else answer is the max distance.Ex:7 71 2 12 7 11 6 -16 5 -15 4 -14 3 -13 1 5here, the +ve cycle affects the 'nth' node.But here,8 91 2 12 3 13 4 14 2 11 8 15 8 15 6 16 7 17 5 1it doesn't affect the nth node.
•  » » » 7 months ago, # ^ |   0 Reason behind marking nodes whose distances are changed in the nth iteration — node which is marked is involved in the cycle. We will print -1 only when it is possible to reach to last node from the cycle. To check whether it is possible to reach to last node from the cycle, there are two ways 1) run dfs from every node which is marked (involved in cycle) and check whether is it possible to reach to nth node, if yes print — 1. 2)reverse the graph and check whether it is possible to reach to atleast one node which is marked from the last node, if yes print -1. Both ways give the same result but the 2nd method is fast. Please ask if you have any doubt(this is my first explanation, I apologize if my explanation is not clear).
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 what if the node (in the cycle and connected to n) is not connected to 1?1 4 12 4 12 3 13 2 1there's a cycle 2 — 3 — 2 and 2 is connected to 4 but even then, answer is still 1 (and not -1) because we can't go to that cyclewhat I did was see everyone that could be in a path from 1 to n, if one of those nodes are in a cycle, answer is -1:run dfs from 1 in original graph, mark everyone connectedrun dfs from n in reversed graph, mark everyone connectedintersection is the vertices that we can use in our path, and if any vertex here is in a cycle, ans is -1
•  » » » 7 weeks ago, # ^ |   0 Nodes that are not reachable from node 1 will always remain unchanged i.e INFINITY in the distance array. so only dfs from n'th node in reverse adj list is fine .
 » 13 days ago, # |   0 it's a simple bellman-ford algorithm int n,m; vector> edges; int dist[2501]; void solve(){ int a,b,c; cin >> n >> m; fill(dist,dist+2501,-INF); dist[1] = 0; for(int i=0;i < m;i++){ cin >> a >> b >> c; edges.pb({a,b,c}); } for(int j=0;j < n-1;j++){ for(int i=0;i < m;i++){ int value = dist[edges[i][from]] + edges[i][weight]; if(dist[edges[i][from]] == -INF) value = -INF; if(value > dist[edges[i][to]]){ dist[edges[i][to]] = dist[edges[i][from]] + edges[i][weight]; } } } for(int j=0;j < n-1;j++){ for(int i=0;i < m;i++){ int value = dist[edges[i][from]] + edges[i][weight]; if(dist[edges[i][from]] == -INF) value = -INF; if(value > dist[edges[i][to]]){ dist[edges[i][to]] = INF; } } } if(dist[n] == INF) cout << -1 << endl; else cout << dist[n] <
 » 25 hours ago, # | ← Rev. 2 →   0 2 1 1 2 -1 Answer is -1, but it isn't infinity score.?