On SPOJ Toolkit, there is this particular test case:
1
42
3 1 19
13 1 34
18 2 89
21 3 94
23 4 59
1 5 38
34 6 75
37 7 33
41 8 60
34 9 71
21 10 27
30 11 84
42 12 27
18 13 89
18 14 36
41 15 31
24 16 53
8 17 27
30 18 74
3 19 41
39 20 32
34 21 65
14 22 28
21 23 65
42 24 53
5 25 81
13 26 69
21 27 41
4 28 96
30 29 39
15 31 51
27 32 18
31 33 53
18 34 20
31 35 93
34 36 61
18 37 71
4 38 50
36 39 63
22 40 27
11 41 27
29 42 69
The answer from the correct program gives 665 (can be tested here). However, I constructed the graph with graphviz and I found the longest path is 677, which is highlighted in red:
The sum of red path: 93 + 51 + 31 + 27 +84 + 74 + 20 + 65 + 94 + 19 + 38 + 81 = 677
The sum of blue path: 93 + 51 + 31 + 27 + 84 + 74 + 20 + 65 + 65 + 59 + 96 = 665
The blue path is the path that gives 665. Is something wrong?