Cod sursa(job #1881206)

Utilizator jordan1998Jordan jordan1998 Data 16 februarie 2017 11:43:49
Problema Algoritmul lui Dijkstra Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define nods 50002
#define buffs 1048576
#define inf 2000000000
using namespace std;
FILE *f=freopen("dijkstra.in","r",stdin);
int n,m,pos=0,a,i,d[nods],viz[nods],mini;
bool ok;
char buff[buffs];
struct gigi
{
    int c,y;
} _x;
std::vector<gigi>v[nods];
inline void read(int &x)
{
    while( buff[pos]<'0'||buff[pos]>'9') if(++pos==buffs) fread(buff,1,buffs,stdin),pos=0;
    x=0;
    while( buff[pos]>='0'&&buff[pos]<='9')
    {
        x=(x<<1)+(x<<3)+buff[pos]-'0';
        if(++pos==buffs) fread(buff,1,buffs,stdin),pos=0;
    }
}
int main()
{
    fread(buff,1,buffs,stdin);
    freopen("dijkstra.out","w",stdout);
    read(n);
    read(m);
    for(i=1;i<=n;i++)
       d[i]=inf;
    for(i=1; i<=m; i++)
    {
        read(a),read(_x.y),read(_x.c);
        v[a].push_back(_x);
    }

//dijkstra
    ok=1;
    viz[1]=1;
    a=v[1].size();
    for(i=0; i<a; i++)
        d[v[1][i].y]=v[1][i].c;

    while(ok)
    {
        mini=inf;
        for(i=1; i<=n; i++)
            if(!viz[i]&&mini>d[i])
            {
                mini=d[i];
                a=i;
            }
        if(mini!=inf)
        {
            viz[a]=1;
            pos=v[a].size();
            for(i=0; i<pos; i++)
                if(!viz[v[a][i].y]&&d[v[a][i].y]>d[a]+v[a][i].c)
                    d[v[a][i].y]=d[a]+v[a][i].c;

                }
        else ok=0;
    }


    for(i=2;i<=n;i++)
        if(d[i]==inf) printf("0 ");
    else
        printf("%d ",d[i]);
}