Vedkribhu's blog

Need Help CSES Graph Problem: High Score
By Vedkribhu, history, 23 months ago, In English

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?

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
23 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain the intuition behind doing this?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 7

      1 2 1

      2 7 1

      1 6 -1

      6 5 -1

      5 4 -1

      4 3 -1

      3 1 5

      here, the +ve cycle affects the 'nth' node.

      But here,

      8 9

      1 2 1

      2 3 1

      3 4 1

      4 2 1

      1 8 1

      5 8 1

      5 6 1

      6 7 1

      7 5 1

      it doesn't affect the nth node.

      → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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).

      → Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    what if the node (in the cycle and connected to n) is not connected to 1?
    1 4 1
    2 4 1
    2 3 1
    3 2 1
    there'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 cycle

    what 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 connected
    run dfs from n in reversed graph, mark everyone connected
    intersection is the vertices that we can use in our path, and if any vertex here is in a cycle, ans is -1

    → Reply
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 .

      → Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    It's a super confusing question as expected from cses: example 1:

    4 4
1 4 1
2 4 1
2 3 1
3 2 1

expected output:
1

example 2:

4 5
1 2 1
2 3 1
3 2 1
2 4 1
1 4 1000000000

expected output:
-1

    WHY?????????

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

it's a simple bellman-ford algorithm

int n,m;
vector<vector<int>> 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] <<endl;
	
	
}
→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
2 1
1 2 -1

Answer is -1, but it isn't infinity score.

?

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

xd

→ Reply