# Problema: Footing **URL:** \ **Category:** Aiuto\ **Created:** [12 Gennaio 2017, 3:40pm UTC](https://forum.olinfo.it/t/problema-footing/4308 "2017-01-12T15:40:40Z")\ **Posts on this page:** 6\ **Page:** 2
**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\ **Post date:** [21 Marzo 2017, 1:55pm UTC](https://forum.olinfo.it/t/problema-footing/4308/21 "2017-03-21T13:55:11Z")
Se parliamo delle territoriali (come nel caso del task footing) allora è importante far notare che l’efficienza non è fondamentale. È importante solo che l’algoritmo sia corretto (e ragionevolmente performante, nel senso: non terribilmente esponenziale). Una soluzione per footing che qui esce dai limiti di tempo, avrebbe tranquillamente preso tutti i punti in gara. Il tempo limite alle territoriali è volutamente alto per far passare soluzioni non efficienti. Se invece parliamo di altre gare, allora la regola è la solita: calcolare la complessità, stimare il tempo d’esecuzione al caso pessimo. Dijkstra (nell’implementazione che conosco io, quella spiegata nel booklet che contiene il task footing) è O(M\log N) dove M è il num di archi e N il num di nodi. ---
**Author:** ![aldo.carrolo](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/3ab097/32.png) [@aldo.carrolo](https://forum.olinfo.it/u/aldo.carrolo)\ **Post date:** [22 Marzo 2017, 3:40pm UTC](https://forum.olinfo.it/t/problema-footing/4308/22 "2017-03-22T15:40:22Z")
Ma è normale che l’algoritmo che ho applicato per risolvere mosaic è il più veloce con 0.004s (@wil93) ? 😂😂 ---
**Author:** ![SimoGiova](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/e9c0ed/32.png) [@SimoGiova](https://forum.olinfo.it/u/SimoGiova)\ **Post date:** [23 Marzo 2017, 10:36am UTC](https://forum.olinfo.it/t/problema-footing/4308/23 "2017-03-23T10:36:12Z")
Scusate l’ignoranza, so come funziona l’algoritmo di dijkstra ma non capisco come è possibile utilizzarlo per rilevare il ciclo minimo all’interno di un grafo. Qualcuno me lo potrebbe spiegare? ---
**Author:** ![aldo.carrolo](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/3ab097/32.png) [@aldo.carrolo](https://forum.olinfo.it/u/aldo.carrolo)\ **Post date:** [23 Marzo 2017, 12:38pm UTC](https://forum.olinfo.it/t/problema-footing/4308/24 "2017-03-23T12:38:09Z")
Il ciclo in un grafo equivale ad il cammino minimo tra A e B (senza passare per l’arco A-B) e la somma dell’arco stesso. L’unica modifica che devi applicare a dijkstra è quella per cui quando inserisci nella coda i vari nodi adiacenti, controlli che il nodo attuale non sia A e il nodo collegato non sia B. Se dijkstra ti restituirà INFINITO vuol dire che non esiste un ciclo tra i 2 nodi. ---
**Author:** ![SimoGiova](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/e9c0ed/32.png) [@SimoGiova](https://forum.olinfo.it/u/SimoGiova)\ **Post date:** [23 Marzo 2017, 7:16pm UTC](https://forum.olinfo.it/t/problema-footing/4308/25 "2017-03-23T19:16:12Z")
penso di aver capito. grazie mille ---
**Author:** ![lukecavabarrett](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lukecavabarrett/32/1753_2.png) [@lukecavabarrett](https://forum.olinfo.it/u/lukecavabarrett)\ **Post date:** [14 Agosto 2017, 4:20pm UTC](https://forum.olinfo.it/t/problema-footing/4308/26 "2017-08-14T16:20:32Z")
È super-necroposting, ma vabbè, leggo ora e volevo aggiungere un paio di cose. Per quanto riguarda il problema Dijkstra sul CMS, la soluzione con tempo minore fatta da Zappia è il classico algoritmo di Dijkstra scritto in Assembly; il secondo tempo migliore è un codice sottomesso da me, dove implemento SPFA al posto di Dijkstra. Quindi nei grafi sparsi, SPFA è veramente più efficiente. [Pagina precedente](https://forum.olinfo.it/t/problema-footing/4308.md?page=1)