Cod sursa(job #2572633)

Utilizator iliescualexiaIliescu Alexia iliescualexia Data 5 martie 2020 13:38:40
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp-64 Status done
Runda OJI 2020 Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define f first
#define s second
#define pinf 2000000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector <pair<int,int> > v[100010];
priority_queue < pair<int,int> ,vector <pair<int,int> >,greater< pair<int,int> > > q;
int n,m,i,j,x,y,c,st,viz[100010], d[100010];
pair<int,int> aux;
void dijkstra(int st)
{
    viz[st]=1;
    for(int i=0;i<v[st].size();i++)
    {
        q.push(v[st][i]);
        d[v[st][i].s]=v[st][i].f;
    }
    for(int i=1;i<n&&!q.empty();i++)
    {
        while(viz[q.top().s]==1&&!q.empty())
        {
           q.pop();
        }
        if(!q.empty())
        {
            aux=q.top();
            q.pop();
        }
        viz[aux.s]=1;
        for(int j=0;j<v[aux.s].size();j++)
        {
            if(viz[v[aux.s][j].s]==0)
            {
                if(d[v[aux.s][j].s]>d[aux.s]+v[aux.s][j].f)
                {
                    d[v[aux.s][j].s]=d[aux.s]+v[aux.s][j].f;
                    q.push(make_pair(d[v[aux.s][j].s],v[aux.s][j].s));
                }
            }
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v[x].push_back(make_pair(c,y));
    }
    for(int i=1;i<=n;i++)
    {
        d[i]=pinf;
    }
    d[1]=0;
    dijkstra(1);
    for(int i=2;i<=n;i++)
    {
        if(d[i]==pinf)
        {
            fout<<0<<" ";
        }
        else
        {
            fout<<d[i]<<" ";
        }

    }
    return 0;
}