I had been solving [High Score](https://cses.fi/problemset/task/1673/) problem. After reading [some](https://codeforces.com/blog/entry/79981) [blogs](https://cp-algorithms.com/graph/bellman_ford.html), I was able to conclude:</ <br/>↵
↵
↵
<b>Claim 1:</b> ConsiderALL```ALL``` cycles ```{ C(i) }``` reachable from source S```S```. In the Bellman Ford Algorithm, ```FOR EVERY``` cycle ```C(i)```,</br>↵
```THERE EXISTS A (``` a vertex) in ```C(i)``` whose distance is modified in the ```nth``` iteration of the Algorithm)↵
↵
<b>Claim 2:</b> If the distance if a vertex is modified in the(nth```nth``` iteration), it must be the part of a negative cycle</br>↵
↵
↵
Can someone please verify ifT```these Cclaims``` are correct? </br/>↵
↵
The Solution idea to [High Score](https://cses.fi/problemset/task/1673/)</br/>↵
Multiply all edge weights by ```-1```, now we need to minimize our score</br/>↵
S: Source Vertex</br />↵
D: Destination Vertex </br />↵
C: A negative weight directed cycle</brbr /><br />↵
```IF:```</br/>↵
* In the ```nth``` iteration if there does not occur any relaxation for any edge, then there is no negative cycle reachable from ```S``` hence the answer ```dist(D)``` from Bellman Ford is the Correct answer </br/>↵
```ELSE:```</br/>↵
* There must exist a negative weight cycle reachable from ```S```. But this does not imply that the Minimum Score to reach ```D``` is ```-INFINITY```</br/>↵
==> It is possible that if we enter the cycle ```C```, it is not possible to reach ```D``` so it we can't keep reducing our score by cycling through the cycle.</br/>↵
* So we need to check if there exits a negative weight cycle ```C``` such that it is possible to reach ```C``` from ```S``` and then reach ```D``` from ```C```. </br/>↵
** If```If``` such a ```C``` exists, the minimum score to reach ```D``` from ```S``` is ```-INFINITY``` </br/>↵
** ```Else,``` bellman ford Gave us th ecorrect answer after the ```nth``` ( or ```(n-1)th``` ) iteration</br/>↵
All test cases passed</br/>↵
Could solmeone Acknowledge if ```Claim 1``` and ```Claim 2``` are correct? I believe they need to be for the correctness of the above mentioned solution.</br/>↵
↵
↵
↵
↵
↵
↵
↵
<b>Claim 1:</b> Consider
↵
<b>Claim 2:</b> If the distance if a vertex is modified in the
↵
↵
Can someone please verify if
↵
The Solution idea to [High Score](https://cses.fi/problemset/task/1673/)<
Multiply all edge weights by ```-1```, now we need to minimize our score<
S: Source Vertex<
D: Destination Vertex <
C: A negative weight directed cycle<
```IF:```<
* In the ```nth``` iteration if there does not occur any relaxation for any edge, then there is no negative cycle reachable from ```S``` hence the answer ```dist(D)``` from Bellman Ford is the Correct answer <
```ELSE:```<
* There must exist a negative weight cycle reachable from ```S```. But this does not imply that the Minimum Score to reach ```D``` is ```-INFINITY```<
==> It is possible that if we enter the cycle ```C```, it is not possible to reach ```D``` so it we can't keep reducing our score by cycling through the cycle.<
* So we need to check if there exits a negative weight cycle ```C``` such that it is possible to reach ```C``` from ```S``` and then reach ```D``` from ```C```. <
All test cases passed<
Could solmeone Acknowledge if ```Claim 1``` and ```Claim 2``` are correct? I believe they need to be for the correctness of the above mentioned solution.<
↵
↵
↵
↵
↵
