Ho un dubbio per quanto riguarda l’esercizio 3. In pratica si aveva un grafo pesato e bidirezionale, e N nodi. Bisognava trovare il percorso chiuso più breve (di almeno tre nodi e passando solo una volta per uno stesso nodo). Io l’ho risolto facendo partire una dfs da ogni nodo, e poi entravo in un determinato nodo solo se la distanza dal nodo di partenza era minore, di quella memorizzata. Se tornavo al nodo di partenza dopo essere passata per almeno 3 nodi, la confrontavo la soluzione globale, con la soluzione temporanea. Secondo voi va bene? (i limiti erano N \le 1000 e numero strade \le 10000). C’era un modo più semplice per risolverlo?
Altra cosa, secondo voi quanti punti servono per essere ripescati dalla classifica nazionale?
Dovrebbe dare il risultato corretto (alla fine le provi tutte), però la complessità mi sembra esponenziale dato che alla peggio visiti tutti i possibili cicli e in un grafo completo hai O(2^n) cicli
Avevo aggiunto anche un uscita, nel caso in cui la distanza corrente fosse maggiore della soluzione migliore trovata fino a quel momento. ma la complessità non dovrebbe essere N*M (*N perchè lo devi ripetere per tutti i nodi, quindi alla fine N^2*M)?
