Cod sursa(job #703937)

Utilizator bogdan353Costea Bogdan bogdan353 Data 2 martie 2012 15:34:01
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

#define nmax 50002
#define pb push_back
#define mp make_pair
#define inf 0x3f3f3f3f


int n,m,cost[nmax],v[nmax],sir[nmax],dimh=0,h[nmax],pozh[nmax];
vector <pair <int , int> > lista[nmax];
ofstream g("dijkstra.out");






void push(int pct)
{
	int tata=pct/2;
	if(pct==1) return ;
	if(cost[h[pct]]>=cost[h[tata]]) return ;
	swap(h[pct],h[tata]);
	swap(pozh[h[pct]],pozh[h[tata]]);
	push(pozh[h[tata]]);
}


void pop(int pct)
{
	int f1=pct*2;
	int f2=pct*2+1;
	int pctmin=pct;
	
	if(cost[h[f1]]<cost[h[pctmin]] && f1<=dimh)
		pctmin=f1;
	if(cost[h[f2]]<cost[h[pctmin]] && f2<=dimh)
		pctmin=f2;
	
	if(pct==pctmin) return;
	
	swap(h[pct],h[pctmin]);
	swap(pozh[h[pct]],pozh[h[pctmin]]);
	pop(pozh[h[pctmin]]);
	
}
	
	





void sterge()
{
	
	swap(h[1],h[dimh]);
	swap(pozh[h[1]],pozh[h[dimh]]);
	dimh--;
	
	
	pop(pozh[h[1]]);
}



void dijkstra()
{
	
	
	
	while(dimh!=0)
	{
		int nod_minim=h[1];
		
		for(unsigned int i=0;i<lista[nod_minim].size();i++)
		{
			int nod=lista[nod_minim][i].first;
			if(v[nod]==1) continue;
			int cost1=lista[nod_minim][i].second;
			int cost_tot=cost1+cost[nod_minim];
			if(cost_tot<cost[nod])
			{
				cost[nod]=cost_tot;
				//sterge(pozh[nod]);
				push(pozh[nod]);
			}
		}
		sterge();
		v[nod_minim]=1;
	}
}
		



int main()
{
	ifstream f("dijkstra.in");
	
	
	f>>n>>m;
	cost[1]=0;
	for(int i=1;i<=n;i++)
	{
		if(i>1)
		cost[i]=inf;
		dimh++;
		pozh[i]=dimh;
		h[dimh]=i;
		push(pozh[i]);
		
	}
	
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		f>>a>>b>>c;
		lista[a].pb(mp(b,c));
		
	}
	
	dijkstra();
	
	for(int i=2;i<=n;i++)
	{
		if(cost[i]==inf)
		{
			g<<"0 ";
			continue;
		}
		g<<cost[i]<<" ";
	}
	
}