Cod sursa(job #2368043)

Utilizator blacktundraTudorescu Ana-Maria blacktundra Data 5 martie 2019 13:28:49
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
#define nmax 50001
#define inf 99999999

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int n,m,r,d[nmax];
bool viz[nmax];

struct arc
{
    int x,c;
};

vector < arc > v[nmax];
queue < int > q;

void dij(int x)
{
    for(int i=1; i<=n; i++)
        d[i]=inf;

    d[x]=0;
    viz[x]=1;
    q.push(x);
    while(!q.empty())
    {
        int i=q.front();
        q.pop();
        r=v[i].size();
        for(int k=0; k<r; k++)
        {
            int j=v[i].at(k).x;
            int l=v[i].at(k).c;
            if(d[j]>d[i]+l)
            {
                d[j]=d[i]+l;
                q.push(j);
                viz[j]=1;
            }
        }
    }
}

int main()
{
    int a,b,val;
    in>>n>>m;
    for(int i=1; i<=n; i++)
    {
        in>>a>>b>>val;
        v[a].push_back( {b,val});
        v[b].push_back( {a,val});
    }
    dij(1);
    for(int i=2; i<=n; i++)
        out<<d[i]<<" ";
    return 0;
}