Pagini recente » Cod sursa (job #1839333) | Cod sursa (job #1782150) | Cod sursa (job #2697411) | Cod sursa (job #440837) | Cod sursa (job #388197)
Cod sursa(job #388197)
#include<fstream>
#define inf "dijkstra.in"
#define outf "dijkstra.out"
#define NMax 50010
#define INF 0x3f3f3f3f
using namespace std;
fstream f(inf,ios::in),g(outf,ios::out);
struct graf
{
int nod,cost;
graf *next;
};
int N,M;
graf *a[NMax];//lista de adiacenta
int d[NMax];
int heap[NMax];//heap[i]=j <=> eticheta nodului i din heap este nodul j din graf
int pos[NMax];//pos[i]=j <=> nodul i din graf este eticheta nodului j din heap
int dim;//numarul de noduri din heap la un moment dat
void add(int unde,int nd,int costarc)//adaug in lista de adiacenta a nodului unde, nodul nd
{
graf *c=new graf;
c->nod=nd;
c->cost=costarc;
c->next=a[unde];
a[unde]=c;
}
void Citire()//citesc datele
{
int x,y,z;
f>>N>>M;
for(int i=1;i<=M;i++)
{
f>>x>>y>>z;
add(x,y,z);
}
for(int i=1;i<=N;i++){d[i]=INF;pos[i]=-1;}//initializez vectorul d cu INF(0x3f3f3f3f)
}
int father(int nodh){return nodh/2;}//tatal nodului nodh din heap
int lson(int nodh){return 2*nodh;}//fiul stang al nodului nodh din heap
int rson(int nodh){return 2*nodh+1;}//fiul drept al nodului nodh din heap
void upheap(int nodh)//"ridic" nodul nodh in heap
{
int tata;
while(nodh>1)
{
tata=nodh>>1; //nodh/2
if(d[heap[nodh]]<d[heap[tata]])
{
pos[heap[nodh]]=tata;
pos[heap[tata]]=nodh;
swap(heap[nodh],heap[tata]);
nodh=tata;
}
else break;
}
}
void downheap(int nodh)//"cern" nodul nodh in heap
{
int f;//fiu
while(nodh<=dim)
{
f=nodh;
if( (nodh<<1)<=dim )
{
f=nodh<<1;//nodh*2
if(f+1<=dim && d[heap[f+1]]<d[heap[f]])f++;
}
else return;
if(d[heap[f]]<d[heap[nodh]])
{
pos[heap[nodh]]=f;
pos[heap[f]]=nodh;
swap(heap[nodh],heap[f]);
nodh=f;
}
else return;
}
}
void Dijkstra()
{
int min;
dim=1;
d[1]=0;
pos[1]=1;
heap[1]=1;
while(dim)
{
min=heap[1];
swap(heap[1],heap[dim]);
pos[heap[1]]=1;
dim--;
downheap(1);
graf *t=a[min];
while(t)
{
if(d[t->nod]>d[min]+t->cost)
{
d[t->nod]=d[min]+t->cost;
if(pos[t->nod]!=-1)upheap(pos[t->nod]);
else
{
heap[++dim]=t->nod;
pos[heap[dim]]=dim;
upheap(dim);
}
}
t=t->next;
}
}
}
void Afisare()
{
for(int i=2;i<=N;i++)
{
if(d[i]==INF)g<<"0 ";
else g<<d[i]<<" ";
}
}
int main()
{
Citire();
Dijkstra();
Afisare();
f.close();
g.close();
return 0;
}