Cod sursa(job #2306250)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 21 decembrie 2018 20:29:24
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include<cstdio>
const int N=50001,I=1<<30;
struct G
{
    int o,c;
    G *n;
};
int n,m,i,x,y,z,d[N],h[N],p[N],k,l;
G *a[N],*q;
void swap(int x, int y)
{
    int t = h[x];
    h[x] = h[y];
    h[y] = t;
}
void upheap(int what)
{
    int tata;
    while(what>1)
    {
        tata=what>>1;
        if(d[h[tata]]>d[h[what]])
            p[h[what]]=tata,p[h[tata]]=what,swap(tata,what),what=tata;
        else
            what=1;
    }
}
void downheap(int what)
{
    int f;
    while(what<=k)
    {
        f=what;
        if((what<<1)<=k)
        {
            f=what<<1;
            if(f+1<=k)
                if(d[h[f+1]]<d[h[f]])
                    ++f;
        }
        else
            return;
        if(d[h[what]]>d[h[f]])
            p[h[what]]=f,p[h[f]]=what,swap(what,f),what=f;
        else
            return;
    }
}
int main()
{
	freopen("dijkstra.in","r",stdin),freopen("dijkstra.out","w",stdout),scanf("%d%d",&n,&m);
    while(m--)
        scanf("%d%d%d",&x,&y,&z),q=new G,q->o=y,q->c=z,q->n=a[x],a[x]=q;
    for(i=2;i<=n;i++)
        d[i]=I,p[i]=-1;
    for(p[1]=h[++k]=1;k;)
        for(l=h[1],swap(1,k),p[h[1]]=1,k--,downheap(1),q=a[l];q;q=q->n)
            if(d[q->o]>d[l]+q->c)
            {
                d[q->o]=d[l]+q->c;
                if(p[q->o]!=-1)
                    upheap(p[q->o]);
                else
                    h[++k]=q->o,p[h[k]]=k,upheap(k);
            }
    for(i=2;i<=n;i++)
        printf("%d ",d[i]==I?0:d[i]);
}