Problema Edifici Universitari


#1

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.


#2

Risolto, avevo fatto un piccolo errore in Dijkstra che mi allungava di molto la visita


#3

Quel 720 si può ridurre di molto (a 15)