Pagini recente » Cod sursa (job #2499405) | Cod sursa (job #1328481) | Cod sursa (job #2036649) | Cod sursa (job #1231105) | Cod sursa (job #1022057)
#include <stdio.h>
#include <algorithm>
using namespace std;
struct nod {int val,pr;nod *urm;};
nod *v[50002];
int h[50002],d[50002],pos[50002],n,n1,cur,m,x,y,pr,i;
FILE *f,*g;
void swap (int i,int j)
{
int aux;
aux=h[i];
h[i]=h[j];
h[j]=aux;
aux=pos[i];
pos[i]=pos[j];
pos[j]=aux;
}
void upheap (int k)
{ int t;
if (k>=1)
{
t=(k-1)/2;
if (d[h[k]]<d[h[t]])
{
swap (k,t);
upheap (t);
}
}
}
void dwheap (int k,int n)
{ int st=0,dr=0;
st=k*2+1;
if (st<=n)
{
dr=k*2+2;
if (dr<=n)
{
swap (min (st,dr),k);
dwheap (min(st,dr),n);
}
else
{
swap (st,k);
dwheap (st,n);
}
}
}
void buildheap (int k)
{
for (i=1;i<=k;i++) upheap (i);
}
void add (int x,int y)
{
nod *t;
t=new nod;
t->val=y;
t->pr=pr;
t->urm=v[x];
v[x]=t;
}
void scot ()
{
swap (1,n);
n--;
dwheap (1,n);
}
int main()
{f=fopen ("dijkstra.in","r");
g=fopen ("dijkstra.out","w");
fscanf (f,"%d%d",&n,&m);
n1=n;
for (i=1;i<=m;i++)
{
fscanf (f,"%d%d%d",&x,&y,&pr);
add (x,y);
}
for (i=1;i<=n;i++)
{
d[i]=0x3f;
pos[i]=i;
h[i]=i;
}
d[1]=0;
buildheap (n);
nod *t;
while (n>=1)
{
scot ();
cur=h[n+1];
for (t=v[cur];t;t=t->urm)
{
if (d[t->val]>d[cur]+t->pr)
{
d[t->val]=d[cur]+t->pr;
upheap (pos[t->val]);
}
}
}
for (i=2;i<=n1;i++)
{
if (d[i]<0x3f) fprintf (g,"%d ",d[i]);
else fprintf (g,"0 ");
}
return 0;
}