009 Algoritmul lui Dijkstra

[•Bogdan_tmm]

Este exagerata limita de timp, din cate am vazut intra mai bine o coada simpla decat un heap.

[•mening12001]

Conform "verificatorului" acest algoritm este gresit (wrong answer)

Asa fiind...poate sa'mi explice cineva unde imi este gresit rationamentul ?

Cod:

#include<iostream.h>
#include<fstream.h>
long long a[9000][9000];
int main()
{int i,j,k,n,m,x,y,z;

	ifstream f("dijkstra.in");
ofstream h("dijkstra.out");
f>>n>>m;

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
	a[i][j]=10000;


for(i=1;i<=m;i++)
{	f>>x>>y>>z;
a[x][y]=z;}
for(k=1;k<=n;k++)	
for(j=1;j<=n;j++)
 if(a[1][k]+a[k][j]<a[1][j]&&i!=k&&j!=k)	
	a[1][j]=a[1][k]+a[k][j];
for(i=2;i<=n;i++)
	h<<a[1][i]<<" ";


	return 0;}

Modificat de Moderator: Nu mai posta consecutiv si foloseste tag-ul [ code ] ... [ / code ] cand scrii surse

[•pauldb]

Fara sa ma uit prea atent observ doua probleme majore in programul tau: folosesti prea multa memorie si complexitate timp prea mare. In rest, poti lua testele (sunt publice) si sa vezi unde nu-ti da bine.

[•maoo]

imi poate spune si mie cineva de ce imi da incorect pe acest cod daca rezultatul e la fel cu cel de la raspunsuri

Cod:

#include<fstream>
#include<cstdio>
#include<vector>
#include<utility>
#define ff it->first
#define ss it->second

using namespace std;
int n,m,a,b,c,d[50005],oo=500000000,h[50010],poz[50010],i,l,nod,dist;
void read(),solve(),percolate(int t),sift(int f);
vector <pair<int,int> > v[50010];


int main()
{
	
	read();
	solve();
	return 0;
}
void read()
{
	ifstream in("dijkstra.in");
	in>>n>>m;
	for(;m;m--)
	{
		in>>a>>b>>c;
		v[a].push_back(make_pair(b,c));
	}
	in.close();
}
void solve()
{
	vector<pair<int,int> >::iterator it;
	ofstream out("dijkstra.out");
	for(i=1;i<=n;i++)
	{
		h[i]=i;
		d[i]=oo;
		poz[i]=i;
	}
	d[1]=0;
	l=n;
	for(;l;)
	{
		nod=h[1];
		dist=d[nod];
		for(it=v[nod].begin();it!=v[nod].end();it++)
			if(d[ff]>dist+ss)
			{
				d[ff]=dist+ss;
				percolate(poz[ff]);
			}
		h[1]=h[l];
		poz[h[1]]=1;
		l--;
		sift(1);
	}
	for(i=2;i<=n;i++)
	{
		if(d[i]==oo)
			d[i]=0;
	}
	for(i=2;i<=n;i++)
		out<<d[i]<<" ";
	out.close();
}
void percolate(int f)
{
	int t,aux;
	for(;;)
	{
		t=f>>1;
		if(d[h[t]]<=d[h[f]])
			return;
		aux=h[t];
		h[t]=h[f];
		h[f]=aux;
		poz[h[t]]=t;
		poz[h[f]]=f;
		f=t;
	}
}
void sift(int t)
{
	int f,aux;
	for(;;)
	{
		f=t<<1;
		if(f>l)
			return;
		if(f<l)
			if(d[h[f]]<d[h[f+1]])
				f++;
		if(d[h[t]]<=d[h[f]])
			return;
		aux=h[t];
		h[t]=h[f];
		h[f]=aux;
		poz[h[t]]=t;
		poz[h[f]]=f;
		t=f;
	}
}

[•PlayLikeNeverB4]

Daca iti da corect pe exemplul de la problema nu inseamna ca iti da pentru toate

Nu introdu toate nodurile de la inceput, doar pe cele pe care le-ai vizitat. Le introduci pe parcurs pe fiecare.
Asta e greseala cea mai mare... In rest, am modificat <= in < si >= in > (nu ma intreba de ce, dar a facut diferenta de la 80 la 90...). N-am putut pana la 100, dar vezi tu...

Sursa ta modificata: http://infoarena.ro/job_detail/527679?action=view-source

[•maoo]

bine dar faza este ca mie imi afiseaza ce trebuie la primul exemplu dar imi zice ca e incorect shi imi ia 10 puncte pe la testu 7
http://infoarena.ro/job_detail/527540 asta e mesajul de la evaluator

[•gabitzish1]

Sa inteleg ca pe testul asta :

Cod:

7 9
1 4 2
1 2 1
2 3 3
4 3 1
3 5 2
5 6 5
6 3 1
3 7 2
1 5 9

rezultatul tau e

Cod:

1 3 2 5 10 5 

si iei 0 puncte pe primul test?

[•PlayLikeNeverB4]

Nu iti afiseaza ce trebuie... Am verificat si eu inainte.

Iti da asa la primul: 1 3 2 5 14 5

Mai verifica odata

[•maoo]

Eu ma gandeam ca este ca la .campion...primul test este ca cel din exemplu shi ala imi dadea bine shi de asta...
Gata am rezolvat ms mult de help

[•notpennysboat]

am si eu o intrebare

Cod:

#include <cstdio>
#include <list>
#include <set>

using namespace std;

int n,m;
int d[50002],inms[50002];

struct Compar{
	bool operator()(int i,int j){
		return d[i]<d[j];
	}
};

list<pair<int,int> > l[50002];
list<pair<int,int> >::iterator it;
multiset<int ,Compar> ms;

void citire(){
	scanf("%d %d",&n,&m);
	int i,x,y,c;
	for(i=1;i<=m;i++){
		scanf("%d %d %d" , &x,&y,&c);
		l[x].push_back(make_pair(y,c));
	}
}

void dijkstra(int rad){
	int i,poz;
	for(i=1;i<=n;i++){
		d[i]=1000000000;
		inms[i]=0;
	}
	inms[rad]=1;
	d[rad]=0;
	ms.insert(rad);
	while(!ms.empty()){
		poz=*ms.begin();
		ms.erase(ms.begin());
		inms[poz]=0;
		for(it=l[poz].begin();it!=l[poz].end();++it)
			if(d[(*it).first]>d[poz]+(*it).second){
				if(inms[(*it).first]==1){
					ms.erase((*it).first);
				}
				else {
					inms[(*it).first]=1;
				}
				d[(*it).first]=d[poz]+(*it).second;
				ms.insert((*it).first);
				
			}
	}
}

void afisare(){
	int i;
	for(i=2;i<=n;i++)
		if(d[i]!=1000000000)
			printf("%d ",d[i]);
		else printf("0 ");
	printf("\n");
}

int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	dijkstra(1);
	afisare();
	return 0;
}

am luat testele si unele dimensiuni imi dau prea mari ... nu reusesc sa gasesc greseala

[•b_polar]

Salut!
De ieri tot încerc să fac un cod de 100 de puncte la această problemă, dar la fiecare implementare primesc TLE pe ultimul test. Am încercat mai multe variante:

Dijkstra cu heap - varianta fara STL
Dijkstra cu heap - varianta cu STL
Bellman-Ford cu coada - putin STL
Bellman-Ford cu coada - mai mult STL
Dijkstra cu coada de prioritati

Am pus aici toate variantele, însă mi-ar fi suficient dacă m-aţi putea ajuta să corectez măcar una dintre ele. Merci anticipat .

[•pykh]

Daca luati 80-90 cu TLE pe ultimele teste incercati sa faceti citirea cu streamuri. Asta a facut diferenta in cazul meu de la 80 la 100.

[•jupanubv92]

Salut!
De ieri tot încerc să fac un cod de 100 de puncte la această problemă, dar la fiecare implementare primesc TLE pe ultimul test. Am încercat mai multe variante:

Dijkstra cu heap - varianta fara STL
Dijkstra cu heap - varianta cu STL
Bellman-Ford cu coada - putin STL
Bellman-Ford cu coada - mai mult STL
Dijkstra cu coada de prioritati

Am pus aici toate variantele, însă mi-ar fi suficient dacă m-aţi putea ajuta să corectez măcar una dintre ele. Merci anticipat .

Si eu m-am chinuit ca tine, am bagat mai multe variante, dar vad ca au micÅŸorat limita de timp. Sursa mea de 100 de anu trecut, ia 80 anul asta  . Cred ca trebuie facut cu zice Alexandru sa citesti cu streamuri sau sa parsezi citirea.

[•PlayLikeNeverB4]

Eu n-am parsat citirea si nici n-am citit cu streamuri si iau 100. Ce-i drept, iau ultimul test cu 500ms = limita (da, stiu ca e doar un timp aproximativ)

[•nicolaetitus12]

a reusit cineva sa faca dijkstra de 100 cu make_heap, push_heap si pop_heap?

[•dushmi]

a reusit cineva sa faca dijkstra de 100 cu make_heap, push_heap si pop_heap?

Eu am facut cu priority_queue si a intrat in timp. M-am uitat pe sursa ta... Incearca sa citesti cu fstream pentru ca merge mai bine pe infoarena uneori

[•nicolaetitus12]

Eu am facut cu priority_queue si a intrat in timp. M-am uitat pe sursa ta... Incearca sa citesti cu fstream pentru ca merge mai bine pe infoarena uneori

Am optimizat toate maruntisurile si nu trece. La sursele mele prostia e ca vreau sa modific costul unui element din heap si sa-i mut pozitia in heap. Asta inseamna sa urmaresc pozitia tuturor elementelor in heap si sa folosesc cand trebuie sa le mut pozitia.
La sursa ta vad ca pur si simplu adaugi acelas nod dar cu alt cost. Daca are distanta mica atunci ajunge in varful heapului, daca nu, se pierde si nu ajunge sa-l procesezi vreodata. O sa incerc make_heap cu idea ta sa vad ce iese.
Multumesc!

[•andunhill]

S-a micsorat limita de timp? Sursa http://infoarena.ro/job_detail/357124?action=view-source lui Andrei Misarca  acum ia numai 90 de puncte http://infoarena.ro/job_detail/584692?action=view-source  . A mai reusit cineva sa ia 100 cu priority_queue recent? Eu nu reusesc sa scot mai mult decat 50, restul TLE  .
Puteti sa va puteti uita peste sursa http://infoarena.ro/job_detail/584658?action=view-source si eventual sa imi spuneti ce sa mai optimizez ?
Multumesc anticipat.

LE: Am descoperit ce nu mergea. Nu inteleg dc trebuie  In loc de < sa pun > pentru a-mi tine elementele sortate crescator.

[•a_h1926]

Am o problema cu algoritmul lui dijkstra folosind heap-urile... Am implementat exact cum este explicat algoritmul, dar iau doar 90 de puncte (pe ultimul test iau TLE), se poate uita cineva peste ultima sursa pe care am trimis-o si sa imi spuna ce am putut gresi sau ce pot eficientiza? Multumesc anticipat.

Link-ul pentru sursa este urmatorul:
http://infoarena.ro/job_detail/594225?action=view-source

[•Oancea.Catalin]

incearca sa modifici citirea... in rest pare ok

[•a_h1926]

Am incercat sa fac cu citirile din C, dar asa iau 80 de puncte 
Daca ai vrut sa spui altceva in legatura cu citirea, te rog fii putin mai explicit. Multumesc.

[•Magnus]

in loc de *2 pune <<1 si in loc de /2 pune >>1
astea sunt operatii pe biti si reprezinta shiftarea numarului la stanga sau la dreapta
l.e.:
trebuia sa verific daca ce spun are efecte majore.
ceea ce am spus mai sus nu te ajuta aici, dar cine stie.
ideea este sa-ti faci un struct edge{int dest,cost};
si in loc de

Cod:

vector <long> G[50005];
vector <long> C[50005];

sa ai

Cod:

vector <edge> G[50005];

ti-am modificat sursa si ia acum 100:
http://infoarena.ro/job_detail/594291

[•MciprianM]

Merge de 100 de puncte si un algoritm in O(V*sqrt(V)+E) - sursa.

[•soriyn]

Cod:

 graf *t = a[pmin];

        while ( t )
        {
            if ( d[ t->nod ] > d[pmin] + t->cost )
                d[ t->nod ] = d[pmin] + t->cost;

            t = t->next;
        }

imi poate explica si mie cineva,linie cu linie, bucata asta de cod din sursa de 40 ? 

Foloseste tag-ul [ code ] [ /code ] cand postezi cod!

[•PlayLikeNeverB4]

Cod:

graf *t = a[pmin];  // declaram un pointer caruia ii atribuim adresa listei cu vecinii nodului pmin (care e cel mai apropiat nod dintre cei nevizitati)

        while ( t ) // cat timp n-am ajuns la capatul listei
        {
            if ( d[ t->nod ] > d[pmin] + t->cost )  // daca drumul catre vecinul curent care trece prin pmin este unul mai scurt decat cel calculat pana acum
                d[ t->nod ] = d[pmin] + t->cost;   //  atribuim noua distanta

            t = t->next; // trecem la urmatorul vecin al lui pmin
        }