Ciao a tutti,
mi servirebbe qualche consiglio per questo problema su cui mi sono bloccato da giorni a 50/100.
La mia soluzione consiste nell’applicare dijkstra da ognuno dei k alloggi come sorgente, trovando non la distanza minima rispetto ad un determinato nodo destinazione bensì a tutti i restanti nodi del grafo.
Dopodiché calcolo tutte le possibili combinazioni di questi k alloggi (inteso come ordine in cui li visito), dato che K è <=6 posso avere al massimo 720 combinazioni.
Per ognuna di queste faccio scorrere le distanze dagli n nodi restanti e sommo la minima distanza del primo e dell’ultimo nodo della combinazione da ognuno di questi, in modo da trovare il risultato che dà somma minore, che verrà a sua volta sommata alla lunghezza del circuito.