soluzioni (non certe) ioi

il prof ci ha dato alcune delle sue soluzioni delle olimpiadi di informatica.
Ecco l'esercizio che mi ha messo particolarmente in difficolta...

Sono date 4 città A,B,C,D e le distanze che le separano attraverso un collegamento diretto sono espresse dalla seguente matrice quadrata

A B C D
A 0 5 4 3
B 5 0 1 2
C 4 1 0 3
D 3 2 3 0

Qual'è la lunghezza complessiva del percorso più breve che partendo da A visita tutte le città senza passare nuovamente per A?

La risposta è 6 perchè da A passi a D(3)D passi a B(2) B passi a C(1)