h3. Explicaţie
Dupa ce parcurgem fiecare drum si incrementam cu $1$ muchiile, valorile acestora sunt:

$muchia 1 (5 -> 4): 9
muchia 2 (4 -> 2): 5
muchia 3 (3 -> 1): 5
muchia 4 (4 -> 6): 5
muchia 5 (1 -> 5): 8$

$muchia 1 (5 -> 4): 9$
$muchia 2 (4 -> 2): 5$
$muchia 3 (3 -> 1): 5$
$muchia 4 (4 -> 6): 5$
$muchia 5 (1 -> 5): 8$

Dupa normalizare, muchiile au valorile:

$muchia 1 (5 -> 4): 0
muchia 2 (4 -> 2): 2
muchia 3 (3 -> 1): 3
muchia 4 (4 -> 6): 4
muchia 5 (1 -> 5): 1$

$muchia 1 (5 -> 4): 0$
$muchia 2 (4 -> 2): 2$
$muchia 3 (3 -> 1): 3$
$muchia 4 (4 -> 6): 4$
$muchia 5 (1 -> 5): 1$

Dupa inmultirea cu $alfa$, muchiile au valorile finale:

$muchia 1 (5 -> 4): (0 * 7574) % 100003 = 0
muchia 2 (4 -> 2): (2 * 1) % 100003 = 2
muchia 3 (3 -> 1): (3 * 66670) % 100003 = 4
muchia 4 (4 -> 6): (4 * 25002) % 100003 = 5
muchia 5 (1 -> 5): (1 * 2) % 100003 = 2$

$muchia 1 (5 -> 4): (0 * 7574) % 100003 = 0$
$muchia 2 (4 -> 2): (2 * 1) % 100003 = 2$
$muchia 3 (3 -> 1): (3 * 66670) % 100003 = 4$
$muchia 4 (4 -> 6): (4 * 25002) % 100003 = 5$
$muchia 5 (1 -> 5): (1 * 2) % 100003 = 2$

Permutarea optima este: $4 5 2 1 6 3$
<tex> \sum_{i=1}^{6} dist(i, p(i)) = 2 + 2 + 4 + 2 + 2 + 4 = 16</tex> si este maxima