infoarena

 const
pinfinit=maxlongint;
type long=1..50000;
     pnod=^nod;
     nod=record
         nod:long;
         i:0..1000;
         urm:pnod;
         end;
     cheie=record
           val:longint;
           poz:long;
           end;
     vec=array[1..50000]of long;
var a:array[1..50000]of pnod;
    d:array[1..50000]of record
                        d:longint;
                        s:0..1;
                        end;
    id:^vec;
    h:array[1..50000]of cheie;
    i,poz,n,m,dheap,he,min:longint;
    p:pnod;
    ok:boolean;
    g:text;
 

coada.push( 1 );
incoada[1] = 1;

while( !coada.empty() ) {
	u = coada.pop(), incoada[u] = 0;
	for( v vecin al lui u )
		if( dist[v] > dist[u] + cost(u,v) ) {
			dist[v] = dist[u] + cost(u,v);
			if( incoada[v] == 0 )
				incoada[v] = 1, coada.push(v);
		}
}

for (int i = 0; i < int(G[nod].size()); ++i)

4 4
1 2 5
1 3 10
3 2 -7
2 4 5

10 11
3 2 1
4 3 1
5 4 1
6 5 1
7 6 1
8 7 1
9 8 1
10 9 1
11 10 1
1 11 1
1 2 10000000

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

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

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

1 3 2 5 10 5 

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

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

vector <edge> G[50005];

 graf *t = a[pmin];

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

            t = t->next;
        }

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
        }

 add(y,x,z); 

priority_queue <nod, vector<nod> , greater<nod> > MINHEAP;