# Problema: Footing

**URL:** <https://forum.olinfo.it/t/problema-footing/4308>\
**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:** 20\
**Page:** 1

<div class="post-metadata">

**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:** [12 Gennaio 2017, 3:40pm UTC](https://forum.olinfo.it/t/problema-footing/4308/1 "2017-01-12T15:40:40Z")

</div>

Per risolvere questo problema ho applicato l’algoritmo di dijkstra per trovare il ciclo minore. Riesco a risolvere soltato 4 casi su 10.  
Questo è il codice:

```
#include <iostream>
#include <fstream>
#include <climits>
#include <queue>

using namespace std;

struct nodo
{
	long long min = LONG_MAX;
	vector<pair<int, int>> connessi;	
};

int N, M;
nodo nodi[1000000];
int da[20000], a[20000], w[20000];

int dijkstra(int da, int a, int w)
{
	queue<int> coda;
	coda.push(da);
	
	nodi[da].min = 0;
	
	while(!coda.empty())
	{
		int attuale = coda.front();
		coda.pop();
		
		for(auto i: nodi[attuale].connessi)
		{
			if(attuale == da && i.first == a)
				continue;

			if(i.second + nodi[attuale].min < nodi[i.first].min)
			{
				nodi[i.first].min = i.second + nodi[attuale].min;
				coda.push(i.first);
			}
		}
	}
	
	return nodi[a].min + w;
}

int main()
{
	ifstream in("input.txt");
	ofstream out("output.txt");
	
	in >> N >> M;
	
	for(int i = 0; i < M; i++)
	{
		in >> da[i] >> a[i] >> w[i];
		
		nodi[da[i]].connessi.push_back(pair<int, int>(a[i],w[i]));
		nodi[a[i]].connessi.push_back(pair<int, int>(da[i],w[i]));
	}
	
	int minore = 1000000;
	
	for(int i = 0; i < N; i++)
	{
		int d = dijkstra(da[i], a[i], w[i]);
		
		if(d < minore)
			minore = d;
			
		for(int i = 1; i <= N; i++)	
			nodi[i].min = LONG_MAX;
	}
	
	out << minore;
}
```

---

<div class="post-metadata">

**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:** [12 Gennaio 2017, 8:10pm UTC](https://forum.olinfo.it/t/problema-footing/4308/2 "2017-01-12T20:10:54Z")

</div>

Negli altri casi cosa ti dà? Risposta errata / tempo limite superato?

A occhio comunque direi che il problema sta nella coda usata: `queue` è first-in first-out, ovvero quando fai pop() prendi il nodo che è stato inserito per primo, tra quelli rimasti. Dijkstra invece sfrutta l’idea di estrarre il nodo “migliore” ad ogni passo.

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [12 Gennaio 2017, 8:12pm UTC](https://forum.olinfo.it/t/problema-footing/4308/3 "2017-01-12T20:12:31Z")

</div>

Un caso di esempio “piccolo” su cui la tua soluzione sbaglia è il seguente:

```
5 6
4 2 1
3 2 1
2 5 1
1 2 1
5 4 1
3 4 1
```

---

<div class="post-metadata">

**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:** [12 Gennaio 2017, 8:35pm UTC](https://forum.olinfo.it/t/problema-footing/4308/4 "2017-01-12T20:35:57Z")

</div>

Grazie per l’esempio. Ora faccio 70/100. L’unica cosa che ho inserito è `d > 0` nell’if `d < minore`.

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [13 Gennaio 2017, 11:11am UTC](https://forum.olinfo.it/t/problema-footing/4308/5 "2017-01-13T11:11:02Z")

</div>

Stai sfruttando il fatto che nell’esempio gli archi avevano tutti peso 1. Non è sempre così, ad esempio:

```auto
6 8
1 6 8
6 5 7
1 5 9
3 1 9
6 4 3
2 3 14
3 5 18
4 1 8

```

Ragiona su quanto ti aveva scritto @wil93.

---

<div class="post-metadata">

**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:** [12 Marzo 2017, 7:28pm UTC](https://forum.olinfo.it/t/problema-footing/4308/6 "2017-03-12T19:28:37Z")

</div>

Sono riuscito a risolvere il problema. L’errore stava nel fatto che andavo in `overflow` e quindi “sballava il risultato finale”. Ora però non riesco a velocizzarlo per risolvere l’ultimo caso.

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [14 Marzo 2017, 7:33am UTC](https://forum.olinfo.it/t/problema-footing/4308/7 "2017-03-14T07:33:12Z")

</div>

Fatico a seguire il tuo ragionamento, anche perché non c’è molto da velocizzare (a patto che l’algoritmo sia corretto e non vada in loop).  
Puoi pubblicare il codice?

---

<div class="post-metadata">

**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:** [14 Marzo 2017, 12:12pm UTC](https://forum.olinfo.it/t/problema-footing/4308/8 "2017-03-14T12:12:56Z")

</div>

Questo è il codice:

```
#include <iostream>
#include <fstream>
#include <climits>
#include <queue>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

struct nodo
{
	long long min = LONG_MAX;
	vector<pair<int, int>> connessi;	
};

int N, M;
nodo nodi[1000000];
int da[10001], a[10001], w[10001];

int dijkstra(int da, int a, int w)
{
	queue<int> coda;
	coda.push(da);
	int i_maggiore;
	
	nodi[da].min = 0;
	
	while(!coda.empty())
	{
		int attuale = coda.front();
		coda.pop();
		
		for(auto i: nodi[attuale].connessi)
		{
			if(attuale == da && i.first == a || (attuale != a && i.first == da))
				continue;

			if(i.second + nodi[attuale].min < nodi[i.first].min)
			{
				nodi[i.first].min = i.second + nodi[attuale].min;
				coda.push(i.first);
			}
		}
	}
	
	return nodi[a].min + w;
}

int main()
{
    freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	
	scanf("%d %d", &N, &M);
	
	for(int i = 0; i < M; i++)
	{
	    scanf("%d %d %d", &da[i], &a[i], &w[i]);
		
		nodi[da[i]].connessi.push_back(pair<int, int>(a[i],w[i]));
		nodi[a[i]].connessi.push_back(pair<int, int>(da[i],w[i]));
	}
	
	int minore = 1000000;
	
	for(int i = 0; i < N; i++)
	{
		int d = dijkstra(da[i], a[i], w[i]);
		
		if(d < minore)
			    minore = d;
			
		for(int i = 1; i <= N; i++)	
			nodi[i].min = 1000000;
	}

	printf("%d", minore);
}

```

la modifica che ho effettuato è a seguente:

```
nodi[i].min = LONG_MAX ==> nodi[i].min = 1000000;
```

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [17 Marzo 2017, 11:10am UTC](https://forum.olinfo.it/t/problema-footing/4308/9 "2017-03-17T11:10:40Z")

</div>

Il problema non è la _lentezza_ dell’ultimo testcase, ma il fatto che produce un risultato _sbagliato_.  
Come ti aveva già scritto in una risposta precedente @wil93, stai implementando in modo scorretto l’algoritmo di Dijkstra.  
In particolare, estrai ogni volta dalla coda il primo nodo presente “fidandoti” che questo sia quello a distanza minore. Tuttavia, non è sempre detto che questa assunzione valga (anzi, in generale non è assolutamente valida). La correttezza dell’algoritmo di Dijkstra, ovvero il fatto che termini determinando effettivamente la distanza minima, si basa sulla garanzia che ad ogni iterazione del ciclo `while` estrai dalla coda l’elemento a distanza minore.

---

<div class="post-metadata">

**Author:** ![db2000](https://forum.olinfo.it/user_avatar/forum.olinfo.it/db2000/32/391_2.png) [@db2000](https://forum.olinfo.it/u/db2000)\
**Post date:** [17 Marzo 2017, 8:00pm UTC](https://forum.olinfo.it/t/problema-footing/4308/10 "2017-03-17T20:00:44Z")

</div>

Usando “Dijkstra” impostato come quello di Aldo però a me dà 90/100, non per il risultato sbagliato ma perché va fuori tempo.  
In effetti, l’algoritmo che usiamo [qui](https://cms.di.unipi.it/#/task/dijkstra/statement) realizza 100 punti, quindi, la domanda è: siamo sicuri che, sebbene non sia il “vero Dijkstra”, non funzioni lo stesso?  
Lo dico perché tempo fa mi è stata passata questa versione di Dijkstra da uno che ha fatto le nazionali, lui non ha mai avuto problemi usandolo (anche in gara), quindi penso che se il problema fosse Dijkstra in sé ce ne saremmo accorti da un po’!

---

<div class="post-metadata">

**Author:** ![gullpet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/gullpet/32/316_2.png) [@gullpet](https://forum.olinfo.it/u/gullpet)\
**Post date:** [17 Marzo 2017, 9:12pm UTC](https://forum.olinfo.it/t/problema-footing/4308/11 "2017-03-17T21:12:24Z")

</div>

Il problema in effetti per quell’ultimo testcase non è Dijkstra in sé (probabilmente con delle implementazioni molto ottimizzate darebbe 100), ma il fatto che comunque vai a provarlo per ogni nodo, il che in alcuni casi può diventare parecchio lento. Tuttavia è possibile velocizzarlo (e non poco) con un piccolo accorgimento (in molti casi continui ad effettuare Dijkstra su un nodo nonostante sia già sicuro che non arriverai alla soluzione ottimale)…

---

<div class="post-metadata">

**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:** [18 Marzo 2017, 2:12pm UTC](https://forum.olinfo.it/t/problema-footing/4308/12 "2017-03-18T14:12:24Z")

</div>

Ho cercato un nuovo algoritmo di dijkstra. Questo è il codice:

```
#include <bits/stdc++.h>

using namespace std;

long long int dist[100100];
bool sptSet[100100];

int minDistance(list<pair<int,int>> graph[], int V)
{
	long long int min = LONG_MAX, min_index;
	
	for (int i = 1; i <= V; i++)
	{
		if (sptSet[i] == false && dist[i] <= min)
			min = dist[i], min_index = i;
	}
	
	return min_index;
}

int dijkstra(list<pair<int,int>> graph[], int src, int fine, int V)
{
	for (int i = 1; i <= V; i++)
		dist[i] = LONG_MAX, sptSet[i] = false;
	
	dist[src] = 0;
	
	for (int count = 0; count < V-1; count++)
	{
		int u = minDistance(graph, V);
		
		sptSet[u] = true;
		
		for (auto i: graph[u])
		{
			if (!sptSet[i.first] && dist[u] != LONG_MAX && dist[u]+i.second < dist[i.first])
				dist[i.first] = dist[u] + i.second;
		}
	}
	
	return dist[fine];
}

int main()
{
	ifstream in("input.txt");
	ofstream out("output.txt");

	int N, M, inizio, fine;
	list<pair<int,int>> graph[100100];
	
    in >> N >> M >> inizio >> fine;
	
	for(int i = 0; i < M; i++)
	{
		int a, b, c;
		in >> a >> b >> c;
		
		graph[a].push_back(make_pair(b,c));
	}
	
	out << dijkstra(graph, inizio, fine, N);
	
	return 0;
}

```

Volevo chiedere perchè, sottomettendolo sull’esercizio Dijkstra, riesco a totalizzare solo 95 punti.

P.S: Chiedo aiuto perchè l’ho cercato di riadattare. Il codice originale lo trovate in questo [link](http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/).

---

<div class="post-metadata">

**Author:** ![MrBrionix](https://forum.olinfo.it/user_avatar/forum.olinfo.it/mrbrionix/32/2373_2.png) [@MrBrionix](https://forum.olinfo.it/u/MrBrionix)\
**Post date:** [18 Marzo 2017, 8:24pm UTC](https://forum.olinfo.it/t/problema-footing/4308/13 "2017-03-18T20:24:11Z")

</div>

Infatti io alle OII ho usato quella versione e ho fatto 100/100 in gara, comunque posso confermare che puó essere molto lento ed è meglio usare una priority\_queue in modo da estrarre dalla coda l’elemento minore (in modo piú efficiente rispetto a come fa aldo.carrolo nell’ultima versione di dijkstra) e rendere tutto piú veloce.

---

<div class="post-metadata">

**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:** [19 Marzo 2017, 11:29am UTC](https://forum.olinfo.it/t/problema-footing/4308/14 "2017-03-19T11:29:03Z")

</div>

Come potrei implementare una priority queue?  
Ho cercato di utilizzare la struttura dati `priority_queue<int, vector<int>, greater<int>>` però non è cambiato nulla.

---

<div class="post-metadata">

**Author:** ![MrBrionix](https://forum.olinfo.it/user_avatar/forum.olinfo.it/mrbrionix/32/2373_2.png) [@MrBrionix](https://forum.olinfo.it/u/MrBrionix)\
**Post date:** [19 Marzo 2017, 12:27pm UTC](https://forum.olinfo.it/t/problema-footing/4308/15 "2017-03-19T12:27:08Z")

</div>

Potresti postare il tuo ultimo codice?

---

<div class="post-metadata">

**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:** [19 Marzo 2017, 12:45pm UTC](https://forum.olinfo.it/t/problema-footing/4308/16 "2017-03-19T12:45:23Z")

</div>

```
int dijkstra(int da, int a, int w)
{
	priority_queue<int, vector<int>, greater<int>> coda;
	coda.push(da);
	int i_maggiore;
	
	nodi[da].min = 0;
	
	while(!coda.empty())
	{
		int attuale = coda.top();
		coda.pop();
		
		for(auto i: nodi[attuale].connessi)
		{
			if(attuale == da && i.first == a || (attuale != a && i.first == da))
				continue;

			if(i.second + nodi[attuale].min < nodi[i.first].min)
			{
				nodi[i.first].min = i.second + nodi[attuale].min;
				coda.push(i.first);
			}
		}
	}
	
	return nodi[a].min + w;
}

```

P.S.: con la modifica sopra citata peggioro in 2 casi con il tempo tempo di esecuzione.  
P.P.S.: me ne sono accorto solo ora che la coda preleva il nodo con numero minore e non con peso minore.

---

<div class="post-metadata">

**Author:** ![MrBrionix](https://forum.olinfo.it/user_avatar/forum.olinfo.it/mrbrionix/32/2373_2.png) [@MrBrionix](https://forum.olinfo.it/u/MrBrionix)\
**Post date:** [19 Marzo 2017, 3:06pm UTC](https://forum.olinfo.it/t/problema-footing/4308/17 "2017-03-19T15:06:24Z")

</div>

Ottieni 95/100 perchè nell’ultimo testacase va in overflow: se sostituisci LONG\_MAX con LLONG\_MAX e facendoti restituire un long long anzichè un int dalla funzione dijkstra dovresti fare 100/100.

Per quanto riguarda il problema footing sono riuscito ad ottenere 100/100 aggiungendo queste ottimizzazioni:  
1\_ mi fermo se il nodo che ho appena considerato è quello di arrivo “a” (perchè sicuramente non posso migliorarlo ulteriormente)  
2\_ dichiaro la variabile “minore” globalmente e nel dijsktra mi fermo se la distanza del nodo su cui sto lavorando rispetto al nodo di partenza “da” è maggiore di “minore” (sicuramente non troverò un percorso migliore)

Inoltre rileggendo il tuo codice ho notato che avevi fatto un errore: nel for che serve a richiamare il dijsktra avevi messo come condizione i\<N anzichè i\<M, in questo modo non considerava tutti gli archi e quindi saltava qualche percorso plausibile.  
Inoltre i ridotto la dimensione di nodi a 1001 dato che ci sono al massimo 1000 nodi.

Ecco il codice:

```auto
#include <iostream>
#include <fstream>
#include <climits>
#include <queue>
#include <stdio.h>
#include <stdlib.h>

using namespace std;
	int minore = 1000000000;
struct nodo
{
	int min = 1000000000;
	vector<pair<int, int>> connessi;	
};

int N, M;
nodo nodi[1001];
int da[10001], a[10001], w[10001];

int dijkstra(int da, int a, int w)
{
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int> > > coda;
	coda.push(pair<int,int>(0,da));
	int i_maggiore;
	
	nodi[da].min = 0;
	
	while(!coda.empty())
	{
	    pair<int,int> temp=coda.top();
		int attuale = temp.second;
		coda.pop();
		
		
		
		for(auto i: nodi[attuale].connessi)
		{
			if(attuale == da && i.first == a || (attuale != a && i.first == da))
				continue;

			if(i.second + nodi[attuale].min < nodi[i.first].min)
			{
				nodi[i.first].min = i.second + nodi[attuale].min;
				coda.push(pair<int,int>(nodi[i.first].min,i.first));
			}
		}
		
		if(attuale==a)
		break;
	if(nodi[attuale].min>minore)
	return 1000000000;
	}
	
	return nodi[a].min + w;
}

int main()
{
    freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	
	scanf("%d %d", &N, &M);
	
	for(int i = 0; i < M; i++)
	{
	    scanf("%d %d %d", &da[i], &a[i], &w[i]);
		
		nodi[da[i]].connessi.push_back(pair<int, int>(a[i],w[i]));
		nodi[a[i]].connessi.push_back(pair<int, int>(da[i],w[i]));
	}
	

	
	for(int i = 0; i < M; i++)
	{
		int d = dijkstra(da[i], a[i], w[i]);
		
		if(d < minore)
			    minore = d;
			
		for(int i = 1; i <= N; i++)	
			nodi[i].min = 1000000000;
	}

	printf("%d", minore);
}

```

---

<div class="post-metadata">

**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:** [19 Marzo 2017, 3:09pm UTC](https://forum.olinfo.it/t/problema-footing/4308/18 "2017-03-19T15:09:46Z")

</div>

> [@MrBrionix](#):
>
> Inoltre rileggendo il tuo codice ho notato che avevi fatto un errore: nel for che serve a richiamare il dijsktra avevi messo come condizione i\<N anzichè i\<M, in questo modo non considerava tutti gli archi e quindi saltava qualche percorso plausibile.

Grazie. Comunque me ne sono accorto ora dell’errore stupido che ho fatto 😵

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [21 Marzo 2017, 8:59am UTC](https://forum.olinfo.it/t/problema-footing/4308/19 "2017-03-21T08:59:33Z")

</div>

Il fatto che questa versione risolvesse correttamente il problema del cammino minimo mi ha incuriosito non poco.

Cercando, ho trovato che questa è l’implementazione di un algoritmo detto SPFA che sta “a metà” tra Dijkstra e Bellman-Ford ([qui](http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm) c’è qualche dettaglio). Da quanto ho potuto capire, la sua complessità computazionale nel caso peggiore è più alta di quella di Dijkstra con una coda di priorità. Tuttavia, _nella pratica_, si comporta meglio di quest’ultimo. Evidentemente ciò è dovuto al minor overhead di una coda semplice rispetto alla coda con priorità.

Nota divertente: “The algorithm was almost certainly popularized by Chinese informatics competitors.” 😂

---

<div class="post-metadata">

**Author:** ![MrBrionix](https://forum.olinfo.it/user_avatar/forum.olinfo.it/mrbrionix/32/2373_2.png) [@MrBrionix](https://forum.olinfo.it/u/MrBrionix)\
**Post date:** [21 Marzo 2017, 12:03pm UTC](https://forum.olinfo.it/t/problema-footing/4308/20 "2017-03-21T12:03:08Z")

</div>

Quindi in gara quale conviene usare? 😓

[Pagina seguente](https://forum.olinfo.it/t/problema-footing/4308.md?page=2)