Problema: Footing

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;
}

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.

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

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

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

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.

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.

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?

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;

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.

2 Mi Piace

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 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’!

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)…

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.

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.

5 Mi Piace

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

Potresti postare il tuo ultimo codice?

4 Mi Piace
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.

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:

#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);
}
5 Mi Piace

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

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 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.” :joy:

1 Mi Piace

Quindi in gara quale conviene usare? :sweat:

4 Mi Piace