Dijkstra (20/100)

Algoritmi
1

Buon pomeriggio,
con questa versione di Dijkstra ottengo solo 20/100. Dove potrebbe essere l’errore?

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <stdio.h>
#include <set>
#include <vector>
#include <climits>

using namespace std;

fstream in,out;

int main(){
	in.open("input.txt",ios::in);
	out.open("output.txt",ios::out);
	
	long long n,m,s,f;
	
	in>>n>>m>>s>>f;
	
	s--;
	f--;
	
	vector <vector < pair<long long,long long> > > grafo(n);
	
	long long i,da,a,peso;
	
	for(i=0;i<m;i++){
		in>>a>>da>>peso;
		a--;
		da--;
		grafo[a].push_back(make_pair(peso,da));
		grafo[da].push_back(make_pair(peso,a));
	}
	
	set <pair <long long,long long> > coda;
	vector <long long> d(n,LLONG_MAX);
	vector <bool> b(n,false);
	d[s] = 0;
	b[s] = true;
	
	coda.insert(make_pair(0,s));
	
	set < pair <long long,long long> > :: iterator it;
	set < pair <long long,long long> > :: iterator itt;
	
	long long x,y,z;
	
	while(!coda.empty()){
		
		it=coda.begin();
		x = (*it).second;
		coda.erase(it);
		
		for(i=0;i<grafo[x].size()i++){
			
			y = grafo[x][i].second;
			z = grafo[x][i].first;
			
			itt=coda.find(make_pair(d[y],y)); 
			
			if( d[y] > d[x]+z ){
                d[y] = d[x] + z;
                if(b[y]){
                    coda.erase(itt);
                }
                else{
                    b[y]=true; 
                }
                coda.insert(make_pair(d[y],y));
            }
		
		}	
	}
	
	out<<d[f];
	
	in.close();
	out.close();
	return 0;
}

Grazie

2

Perchè usi un set al posto di una priority_queue?

1 Mi Piace
3

soltanto una mia abitudine, ho più esperienza con il set piuttosto che con la priority-queue. Non sono molto simili?

4

La mia implementazione di Dijkstra usa una set invece che una priority queue, ha dato 100/100 quindi non penso sia quello il problema, ora mi leggo il codice

5

Non capisco quel vector di booleane a che ti serve

6

Ho tolto il vector bool e cambiato così:

while(!coda.empty()){
		
		it=coda.begin();
		x = (*it).second;
		if(x==f) break;
		coda.erase(it);
		
		for(i=0;i<grafo[x].size();i++){
			
			y = grafo[x][i].second;
			z = grafo[x][i].first;
			
			itt=coda.find(make_pair(d[y],y)); 
			
			if( d[y] > d[x]+z ){
                d[y] = d[x] + z;
                if( itt != coda.end() ){
                    coda.erase(itt);
                }
                coda.insert(make_pair(d[y],y));
            }
		
		}	
	}

ma ottengo sempre 20/100

7

Il grafo è orientato :slight_smile:

2 Mi Piace
8

Ciao, noto adesso che non hai letto bene il testo del problema (seppur non sia poi così lungo).
Il grafo è diretto, quindi orientato e quindi quel “grafo[da].push_back(make_pair(peso,a))” non dovrebbe affatto esserci

9

che disattenzione … grazie ad entrambi

10

io al posto di !coda.empty() come condizione di uscita dal while mi metterei in un vettore booleano se appunto ho esplorato il nodo. quindi non appena esplora il nodo a cui deve arrivare esce. Per fare ciò però devi usare un heap. In questo modo secondo me è molto più veloce perché non hai bisogno di esplorare tutti i nodi, ma non appena arriverai al nodo finale avrai già trovato la tua soluzione. Ho fatto 90 su 100 a quel problema :sweat_smile:

11

Beh, se hai fatto 90, non deve essere difficile fare 100;
Fammi indovinare… Non hai usato i long long

12

dal basso della mia ignoranza purtroppo devo solo
ammetterlo :joy: