Ciao a tutti, volevo provare ad usare il forum in quanto non riuscivo a risolvere l’esercizio footing (nella sezione territoriali 2016).
All’inizio, avendo letto male il problema, ho provato a risolverlo trovando il ciclo dal peso minore passante per il nodo 1. Per fare ciò ho usato più volte l’algoritmo di dijkstra partendo da tutti i nodi collegati a 1 e, per ciascun nodo, inserendo manualmente nella coda tutti i nodi adiacenti eccetto 1, in modo da poter trovare il percorso più veloce per raggiungere 1 partendo da un nodo n senza passare per il collegamento tra i due, per poi aggiungere il valore del collegamento alla lunghezza del percorso (sono piuttosto sicuro che ci siano metodi migliori, ma non ci ho pensato molto su in quanto rileggendo il problema mi sono accorto dell’errore).
Immagino che per gestire un problema simile bisogna usare un qualche tipo di cycle detection, ma non essendo ancora molto bravo a lavorare con i grafi non saprei come fare, qualcuno potrebbe darmi qualche consiglio? (E magari suggerirmi anche qualche modo per ottimizzare il mio algoritmo iniziale?)
In my opinion hai scelto il problema piu difficile tra quelli delle territoriali.
La tua prima idea comunque non e’ cosi male, se la estendi e la fai per ogni arco e non solo per quelli collegati a 1, ti viene una soluzione corretta in O(M^2 \cdot log(N)), che pero’ e’ una complessita’ troppo alta e non sta nel tempo.
Hint: Trova un modo di risolvere il problema con N dijkstra invece che M
Heila, innanzitutto dovresti trovare il ciclo minimo, non necessariamente passante per 1.
Semplicemente puoi risolverlo con dijkstra, pensa ad un modo che ti consente di trovare il percorso da A a B non contando il collegamento tra loro.
Heila, Io l’ho risolto in \mathcal O(E *(E *logV+V)))
weak testcases smh…
nel caso ti scrivo in privata e ti spiego come lho risolto