CSES 1673 High Score - Negating Weights

To find the maximum score path, negate all edge weights and find the minimum path. If the original edge has weight $w$, use weight $-w$ in Bellman-Ford. The shortest path in the converted graph is the longest path in the original. This works because minimizing $-w_1 - w_2 - w_3$ is the same as maximizing $w_1 + w_2 + w_3$.

After finding the shortest path with negated weights, negate the result to get the maximum score. If dist[n] = -10 in the converted graph, the maximum score in the original is $10$.