Here's the way I solve it.
At first, because the problem description said that we could use BFS and Dijkstra, I try to do something similar to Dijkstra. Except that, as anyone said, it doesn't work for longuest path finding.
Does anyone manage to do some Dijkstra like algo?
Then, I did a BFS with the following logic: if the node I'm in was already visited with a higher score, I won't explore this path any further.
With that logic, all tests pass, except the last one.
Funny thing is: by changing the BFS to a DFS, it works for all tests. That's strange because it's BFS that it's advised in the description.