Dijkstra 65/100 non capisco

Non riesco a capire perché 65/100, qualcuno mi può aiutare?

#include <fstream>       
#include <list>         
#include <queue>         
using namespace std;
#define MAX 10001

struct nodo{
	int n;
	long long p;
};
  	
  	list<nodo> liste[MAX];
	queue<int> coda;

  	long long cam[MAX];
	int prov[MAX];
  	bool vis[MAX];
  	int N,S,D,a,b,corrente,p;
	long long x,i,c,M,l;
  	nodo n1;
	ifstream in ("input.txt");
	ofstream out ("output.txt");
	
int main ()
{
	for (i=1;i<=N;i++){
		cam[i]=0;
		vis[i]=false;
	}
  	in>>N>>M; 
  	in>>S>>D; 
  	for (i=0;i<M;i++) {
		in>>a>>b>>c;
		n1.n=b;
		n1.p=c;
		liste[a].push_back(n1);
	}
	coda.push(S);
 	do{
 		corrente=coda.front();
    	        coda.pop();
		if (!vis[corrente]){
			for (list <nodo>::iterator l = liste[corrente].begin(); l!=liste[corrente].end();l++){
				x=cam[corrente]+(*l).p;
				if (cam[(*l).n]==0||cam[(*l).n]>x){
					prov[(*l).n]=corrente;
					cam[(*l).n]=x;
				}
				coda.push((*l).n);
			}	
			vis[corrente]=true;
		}
	} while (!coda.empty());
	out<<cam[D];
  	return 0;
}

Ciao,
ho notato che nella tua implementazione non fai uso di una priority_queue, penso che il problema possa essere causato da quello, hai provato ad utilizzarla?

2 Mi Piace

Che errore ottieni nei testcase che sbagli?

2 Mi Piace

Output non corretto in 7 casi su 20

Perchè usare priority_queue?

Perchè dijkstra si basa sulla priority queue, usando una coda nurmale quello che stai scrivendo è in realtà una visita in ampiezza.

2 Mi Piace

ok, ci provo, grazie.