Pagini recente » Cod sursa (job #2582543) | Cod sursa (job #1944619) | Cod sursa (job #1367006) | Cod sursa (job #3153478) | Cod sursa (job #426284)
Cod sursa(job #426284)
#include<fstream.h>
#define inf 500000000
struct nod { int info,cost; nod *next;};
nod *v[50005];
int m,n,k,dist[50005],h[50005],poz[50005];
void afisare ()
{
int i;
ofstream g("dijkstra.out");
for (i=2;i<=n;i++)
if (dist[i]==inf)
g<<0<<' ';
else
g<<dist[i]<<' ';
g.close();
}
void urca (int k)
{
int x=k;
while (x>1 && dist[h[x]]<dist[h[k>>1]])
{
poz[h[k]]=k>>1;
poz[h[k>>1]]=k;
h[k]=(h[k]^h[k>>1])^(h[k>>1]=h[k]);
}
}
void coboara ()
{
int x=k,y=1;
while (x!=y)
{
x=y;
if (x<<1<=k && dist[h[x]]>dist[h[x<<1]]) y=x<<1;
if (1+x<<1+1<=k && dist[h[x<<1+1]]<dist[h[y]]) y=x<<1+1;
poz[h[x]]=y;
poz[h[y]]=x;
h[x]=(h[x]^h[y])^(h[y]=h[x]);
}
}
void djikstra ()
{
int i,min;
nod *q,*p;
for (i=2;i<=n;i++)
dist[i]=inf;
for (i=1;i<=n;i++)
poz[i]=0;
for (p=v[1];p;p=p->next)
{
dist[p->info]=p->cost;
h[++k]=p->info;
poz[p->info]=k;
urca (k);
}
while (k)
{
min=h[1];
h[1]=h[k--];
poz[h[1]]=1;
coboara();
for (q=v[min];q;q=q->next)
if (dist[q->info]>dist[min]+q->cost)
{
dist[q->info]=dist[min]+q->cost;
if (poz[q->info])
urca (poz[q->info]);
else
{
poz[q->info]=++k;
h[k]=q->info;
urca (k);
}
}
}
}
void citire ()
{
int i,x,y,c;
nod *p;
ifstream f("dijkstra.in");
f>>n>>m;
for (i=1;i<=m;i++)
{
f>>x>>y>>c;
p=new nod;
p->info=y;
p->cost=c;
p->next=v[x];
v[x]=p;
}
f.close();
}
int main()
{
citire ();
djikstra ();
afisare ();
return 0;
}